The Best Team
Time Limit: 1000ms
Memory Limit: 65536kb
DescriptionTo 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?
InputThere 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.
OutputFor 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".
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
p1 p2 p3 happyhap oldbig xiaoga