Problem1060--堆石子

1060: 堆石子

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

在一片沙滩上摆放着n堆石子。 现要将石子有次序地合并成一堆。 每次任选2堆石子合并成新的一堆,合并的费用为新的一堆石子数。试设计一个算法,计算出将n堆石子合并成一堆的最小总费用。

Input

输入数据第1行有1个正整数 n1n≤100000),表示有 n堆石子,每次选2堆石子合并。第2行有 n个整数, 分别表示每堆石子的个数(每堆石子的取值范围为[1,1000]) 。

Output

数据输出为一行, 表示对应输入的最小总费用。

Sample Input Copy

7
45 13 12 16 9 5 22

Sample Output Copy

313

Source/Category

简单 STL