Description

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

Input Format

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

Output Format

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

3
1 6 2

12