Best Relay Team

You coach the national athletics team and have to choose the sprinters who will represent your country in the 4 × 100 m relay at the coming championships.

As the name says, the relay has four legs of 100 meters each. Picking the four fastest 100 m runners in the nation looks right, but one detail changes the answer: the flying start. On the 2nd, 3rd and 4th legs the runner is already running when the baton arrives, so a runner with a slow acceleration phase does relatively better on one of those legs.

You have a pool of runners to choose from. Given how fast each runner is, decide which four runners make the team and which leg each of them runs. Two times are given for every runner: the time to run the 1st leg, and the time to run any of the other legs. A runner on the team runs exactly one leg.

The time of a team is the sum of its four leg times. Find the fastest team.

The first line contains an integer $n$, the number of runners to choose from ($4 \le n \le 500$). Each of the next $n$ lines describes one runner. The $i$-th of those lines contains the name of runner $i$, the time $a_i$ for that runner to run the 1st leg, and the time $b_i$ for that runner to run any of the other legs ($8 \le b_i \le a_i < 20$), separated by spaces. A name is a string of 2 to 20 uppercase letters 'A' to 'Z', and no two runners have the same name. The times are given in seconds with exactly two digits after the decimal point.

On the first line, print the time of the fastest team in seconds with exactly two digits after the decimal point. Then print four lines with the names of the runners on that team, the 1st leg first and the 4th leg last.

If several teams share the fastest time, print the team whose four names, listed from the 1st leg to the 4th leg, form the lexicographically smallest sequence. Names are compared as strings of uppercase letters in dictionary order.