题目描述

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

合并规则如下：

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

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

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

如：麦子的初始总堆数为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

2021 年 10 月 24 日 STEMA