[Login|Register]
Problems

Status

Rank

Problem 1040
The Best Team
Time Limit: 1000ms
Memory Limit: 65536kb
Description
To succeed in ACM programming contests, programming skills in many aspects are needed: dynamic programming, search techniques, computing geometry, combinatorial mathematics, data structure, graph theory, etc. It is not likely for one student to master all these in a short time, but fortunately, the contest is not one person's business, it is a competition between teams of 3 students. So even three students are not the best of all, they can still make up a competitive team since each may have some special skills.
As you may know, gzsun is responsible for constituting 2 or 3 teams for our USTC to attend the coming ACM ICPC regional contest. But since there are so many excellent students, it is hard to select the best team. Gzsun is in trouble now. Can you help him?
Input
There are several cases. Every case starts with n(3<=n<=100), the number of students. The next n lines each will start with a name, followed by 6 integers (between 0 and 9) denoting the student's skillful degrees in dynamic programming, search techniques, computing geometry, combinatorial mathematics, data structure, graph theory. The name is a string consisting of at most 20 letters or digits.
The skillful degree of a special subject of a team is evaluated by the maximum among the team members, not the sum of the team members. The best team is the team with the highest sum of the skillful degrees of 6 subjects.
The input is ended by n = 0.
Output
For each case, print the team members' names of the best team on a separate line. The three names should appear in alphabetical order. There should be a blank between the names.
If there is more than one solution, print the first team appearing in alphabetical order. For example, in the second case in Sample Input, you should print "happyhap oldbig xiaoga" rather than "oldbig xiaoga zizi".
Sample Input
3
p1 1 2 3 4 5 6
p2 0 1 2 3 4 5
p3 0 1 2 3 4 5
6
train 6 6 7 7 8 8
xiaoga 9 9 3 3 4 4
oldbig 2 2 9 9 5 5
simple 5 5 6 6 7 7
happyhap 4 4 5 5 9 9
zizi 4 4 5 5 9 9
0
Sample Output
p1 p2 p3
happyhap oldbig xiaoga
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).