编程实现：合并麦子

题目描述：

秋天是个收获的季节，收获“成熟”的季节，收获“金色”的季节。农民伯伯开始收麦子了，为了省力农民伯伯每收割一部分麦子都会堆放一堆，然后再将所有堆放的麦子按照两两合并的规则合并成一大堆，依此类推，最后运回家。

合并规则如下：

1. 每次只能将两堆麦子合成一堆；
   

   Copy

2. 每次合并麦子都会消耗体力，所消耗的体力为每次所合并的两堆麦子重量之和。
   

   Copy

在给出麦子初始的总堆数及每堆麦子的重量，按照合并规则将每堆麦子两两合并，最后合成一堆，并使最后所消耗的体力最少。 （不考虑每堆麦子之间的距离等因素）

如：麦子的初始总堆数为3，每堆麦子重量分别为1，2，4，按照合并规则有三种方案：

第一种：将重量为1和2的麦子合并，合并出新的一堆麦子，其重量为3，消耗体力为3；再将新合并重量为3的一堆麦子和原来重量为4的一堆麦子合并，合并出新的一堆麦子，重量为7，消耗体力为7。故两次合并共消耗体力3+7=10； 第二种：将重量为1和4的麦子合并，合并出新的一堆麦子，其重量为5，消耗体力为5，再将新合并重量为5的一堆麦子和原来重量为2的一堆麦子合并，合并出新的一堆麦子，重量为7，消耗体力为7。故两次合并共消耗体力5+7=12 第三种：将重量为2和4的麦子合并，合并出新的一堆麦子，其重量为6，消耗体力为6，再将新合并重量为6的一堆麦子和原来重量为1的一堆麦子合并，合并出新的一堆麦子，重量为7，消耗体力为7。故两次合并共消耗体力6+7=13； 根据要求使得最后所消耗的体力最少，所以选择第一种方案，故最少消耗体力为10。

​输入描述：​第一行输入一个正整数n（2<n<1000），表示麦子的总堆数

第二行输入n个正整数表示每堆麦子的重量（重量也表示所要消耗的体力，0<正整数<10^5^），正整数之间以一个空格隔开

​输出描述：​输出一个正整数表示按照合并规则对n堆麦子合并，得到最少消耗体力值

​样例输入：​3

1 6 2

​样例输出：​12

评分标准： （下列各评分项单独计分，得分累加；共 35 个计分点）

7分：能正确输出一组数据；

7分：能正确输出两组数据；

7分：能正确输出三组数据；

7分：能正确输出四组数据；

7分：能正确输出五组数据。

Limitation

1s, 1024KiB for each test case.