文理学院程序设计在线练习


合并礼物

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 24   Accepted Submission(s): 20
Problem Description

有n种礼物,每种礼物的个数分别是m1,m2,..mn,现要将这些礼物通过n-1次的合并合成一堆,假设每个礼物的重量都为1,将两堆礼物合并到一起,消耗的体力等于两堆礼物的重量之和,请设计出合并的次序方案,使得消耗的体力最小,并输出这个最小的体力消耗值。

Input

一组测试数据包括两行,第一行是一个整数n(1<=n<=100),表示礼物的种类数。第二行包含n个整数,分别表示第1,2,3,…,n种礼物的数目。测试数据有多组,处理到文件尾。

Output

每组测试对应一行输出,输出最小的体力消耗值。

Sample Input
2
4 5
3
1 2 9
7
2 3 1 6 8 6 9
Sample Output
9
15
91