Problem22763--石子合并

22763: 石子合并

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

Submit

Description

 在一个建筑工地上有许多堆石子,为了建筑的需要,要把所有的石子合成一堆。

      每一次合并,可以把两堆石子合并到一起,得到新的一堆石子,新堆石子的重量等于原来两堆石子的重量的和,合并这两堆石子消耗的体力等于原来两堆石子的重量之和。可以看出,所有的石子经过n-1次合并之后,就只剩下一堆了。在合并石子时总共消耗的体力等于每次合并所耗体力的和。

      假定已知每堆石子的重量,你的任务是设计出合并的次序方案,使合并石子时耗费的体力最少,输出这个最小的体力耗费值。

      例如有3堆石子,每堆石子的重量依次为285。可以先将13堆合并,新堆的重量为7,耗费体力为7。接着,将新堆与原先的第二堆合并,又得到新的堆,重量为15,耗费体力为15。所以总共耗费体力=7+15=22。可以证明22为最小的体力耗费值。

Input

 从文件shizi.in中读入数据,文件中包括两行,第一行是一个整数n(1<n<=10000),表示原来石子的堆数。第二行包含n个整数,用空格分隔,第i个整数ai(1<ai<=20000)是第i堆石子的重量。

Output

 结果输出到文件shizi.out中,只有一个整数,表示最小的体力耗费值。输入数据保证这个值小于231

Sample Input Copy

3 
2  8  5 

Sample Output Copy

22 

HINT

说明:
对于30%的数据,保证有n<=1000: 
对于50%的数据,保证有n<=5000; 
对于全部的数据,保证有n<=10000。 

Source/Category