Xiao Ming loves a game called "Football Manager"(FM). In this game, you are a manager of a football team. You can buy or sell players, set the formation of the team, set which player to play which position. Xiao Ming is not so good at setting the formation, so he always uses a software called FM scout to help him set the formation and choose players. But by using this software, he loses most of the games. Then he start to doubt the algorithm of the software, and invite you to help him write a program for choosing the formation and the players.
As we all know, there is 11 players on the field for each team, and each player will play a specific position. We consider that only 8 positions, goalkeeper(GK), defender of center(DC), defender of left(DL), defender of right(DR), midfielder of center(MC), midfielder of left(ML), midfielder of right(MR), forward striker(FS), for simple. And there are several formations can be chosen.
Formation A:4-4-2 has 1GK, 2DCs, 1DL, 1DR, 2MCs, 1ML, 1MR, 2FSs
Formation B:4-5-1 has 1GK, 2DCs, 1DL, 1DR, 3MCs, 1ML, 1MR, 1FS
Formation C:4-3-3 has 1GK, 2DCs, 1DL, 1DR, 3MCs, 3FSs
Formation D:3-5-2 has 1GK, 3DCs, 3MCs, 1ML, 1MR, 2FSs
Formation E:3-6-1 has 1GK, 3DCs, 4MC, 1ML, 1MR, 1FS
Formation F:5-3-2 has 1GK, 3DCs, 1DL, 1DR, 3MC, 2FSs
Formation China:6-3-1 has 1GK, 4DCs, 1DL, 1DR, 3MC, 1FS
Each player has a point in each position, which stands for how good he plays in that position. The higher point the player gets, the better he plays in that position. As the same, the higher point the formation gets, the better the it is. You need to find out the best formation form the upper 7 formations for the team, and calculate the total points of this formation by adding the points of 11 positions.
The input file will contain multiple test cases . Each test case will consist of several lines. The first line of each test case contains one integer N(11<=N<=500), which is the number of the plays in the team. The next N lines represent the status of N players. In each line, there are 9 values seperated by a single blank. The first value is a string for the name of the player, while the next 8 values are the points this player plays in GK, DC, DL, DR, MC, ML, MR, FS, which is an integer less than 100. A single line with the number "0" marks the end of input; do not process this case.
For each input test case, output "Formation x has the highest points n". x means the type of the formation, while n means the points this formation has. If several formations has the same points, output them all in the given order in different lines. Leave a single empty line at the end of each case.
12 Ronaldo 0 0 0 0 0 0 0 99 Ronaldinho 0 0 0 0 99 95 95 90 Ronaldo.C 0 0 0 0 90 98 99 80 Henry 0 0 0 0 80 85 85 99 Terry 0 99 90 90 80 0 0 0 Puyol 0 99 90 90 80 0 0 0 Kaka 0 0 0 0 99 95 95 95 Ribery 0 0 0 0 90 99 98 0 Evra 0 90 99 90 0 85 85 0 Alves 0 90 90 99 0 85 85 0 Casillas 99 0 0 0 0 0 0 0 Liyi 30 40 40 40 40 50 50 55 0
Formation A has the highest points 1089.
Migrated from old NTUJ.
2009Harbin
| No. | Testdata Range | Score |
|---|