Tags :
Accepted rate : 199人/213人 ( 93% ) [非即時]

Content

The problem name reﬂects your task; just add a set of numbers. But you may feel yourselves condescended, to write a program just to add a set of numbers. Such a problem will simply question your erudition. So, let us add some ﬂavor of ingenuity to it.

Addition operation requires cost now, and the cost is the summation of those two tobe added. So, to add 1 and 10, you need a cost of 11. If you want to add 1, 2 and 3.

There are three ways:

(1) 1 + 2 = 3, cost = 3; 3 + 3 = 6, cost = 6; Total = 9
(2) 1 + 3 = 4, cost = 4; 4 + 2 = 6, cost = 6; Total = 10
(3) 2 + 3 = 5, cost = 5; 5 + 1 = 6, cost = 6; Total = 11

Your task is write a program to add a set of integers so that the cost is minimized.

Input

Each test case will start with a positive number n, 2 <= n <= 5000, and followed by n  positive integers ki, ki< 100000. Input is terminated by a case where the value of n is zero. This case should not be processed.

Output

For each case, output the minimum total cost of addition in a single line.

Sample Input #1
3
1 2 3
4
1 2 3 4
5
10 5 7 13 11
0
Sample Output #1
9
19
104

Hint ：

10 5 7 13 11

10+11 = 21

12+13 = 25

21+25 = 46

Tags:

[管理者：
(囧rz)
]

 ID User Problem Subject Hit Post Date 12921 (tntchn) b606 496 2017-11-05 23:28