Picture by Fernando Frazão/Agência Brasil, cc by
You are the coach of the national athletics team and need
to select which sprinters should represent your country in the
m relay in
the upcoming championships.
As the name of the event implies, such a sprint relay
consist of legs,
meters each. One
would think that the best team would simply consist of the
fastest m runners in the nation, but
there is an important detail to take into account: flying
start. In the nd,
rd and th leg, the runner is already
running when the baton is handed over. This means that some
runners – those that have a slow acceleration phase – can
perform relatively better in a relay if they are on the
nd, rd or th leg.
You have a pool of runners to choose from. Given how fast
each runner in the pool is, decide which four runners should
represent your national team and which leg they should run. You
are given two times for each runner – the time the runner would
run the st leg, and the
time the runner would run any of the other legs. A runner in a
team can only run one leg.
Input
The first line of input contains an integer , the number of runners to choose
from (). Then follow lines describing the runners. The
’th of these lines
contains the name of the ’th runner, the time for the runner to run the
st leg, and the time
for the runner to
run any of the other legs (). The names consist of between
and (inclusive) uppercase letters
‘A’-‘Z’,
and no two runners have the same name. The times are given in
seconds with exactly two digits after the decimal point.
Output
First, output a line containing the time of the best team,
accurate to an absolute or relative error of at most
. Then output
four lines containing the names of the runners in that team.
The first of these lines should contain the runner you have
picked for the st leg,
the second line the runner you have picked for the nd leg, and so on. Any solution
that results in the fastest team is acceptable.
Sample Input 1 |
Sample Output 1 |
6
ASHMEADE 9.90 8.85
BLAKE 9.69 8.72
BOLT 9.58 8.43
CARTER 9.78 8.93
FRATER 9.88 8.92
POWELL 9.72 8.61
|
35.54
CARTER
BOLT
POWELL
BLAKE
|
Sample Input 2 |
Sample Output 2 |
9
AUSTRIN 15.60 14.92
DRANGE 15.14 14.19
DREGI 15.00 14.99
LAAKSONEN 16.39 14.97
LUNDSTROM 15.83 15.35
MARDELL 13.36 13.20
POLACEK 13.05 12.55
SANNEMO 15.23 14.74
SODERMAN 13.99 12.57
|
52.670000
MARDELL
POLACEK
SODERMAN
DRANGE
|