54 - ZJPCPC Sunny Cup 2006, Online Round - 1005
Our school has decided to hold a basketball invitational tournament to celebrate her 110th anniversary. Some famous NBA teams will be invited to the game.
The tournament will rank the teams by their strength. In order to save time, it is assumed that the strength relation of the teams is transitive, that is, if team A is stronger than B, then A is stronger than any team that is weaker than B. The strength of two teams could be determined by a match between them as a basketball match will never tie, or by the above transitivity.
The teams will be paid for every appearance in the tournament, so for each game, the appearance fee needed is the sum of the appearance fee of the two opponents. The committee has acquired information of the appearance fee of every team for each game, now they want to know the MINIMUM of fund needed to pay the teams in WORST case.Input
The test case consists of up to 10 test cases, and each test case starts with a positive integer N - the number of the teams invited, 1 <= N <= 6. The following line contains N positive integers - the appearance fee of the teams (of thousand dollars), these numbers will not exceed 1000 and are separated by white spaces. The test case ends with 0(zero), which should not be processed.Output
For each test case, output the minimum of fund needed on a single line.Sample Input
3 10 20 30 4 10 10 10 10 0Sample Output
120 100Hints of the sample:
First sample: To rank the 3 teams, each team needs to play against the other two in worst case, and there will be 3 matches in total.
Second sample: One way to do this is to find the rank of three of the teams at first, which takes 3 matches in worst case. Then, play the fourth team against the middle one of those three teams. Finally, if the fourth team comes after the middle team, play it against the last team, while it comes before the middle team, play it against the first team. So 5 matches are needed in worst case, and each match needs 20 thousand dollar, resulting 100 thousand in total.
Author: YANG, Chao