问题描述

具体描述见教材p104：在一个果园里， 多多已经将所有的果子收了下来， 而且按果子的不同种类分成不了同的堆。多多决定把所有的果子合成一堆。 每次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重要之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗的体力之和。 设计一种最省体力的合并方案。 如有三种果子， 数目分别是1，2，9，可以先将1，2合并，新堆数目为3，耗费体力3。接着，将新堆和第三堆合并，得到新堆，数目为12，耗费体力12。所以共耗费体力：3+12=15。

格式

输入

第1行是一个整数$n(1<=n<=10000)$，表示果子的种类数。第2行包含$n$个整数，用空格分隔，第$i$个整数$a_i(1<=a_i<=20000)$是第i种果子的数目。

输出

只包含一个数据，也就是最小的体力耗费值。输入数据保证这个值小于$2^{31}$。

样例

3
1 2 9

15

限制

1s, 64MB.