描述

在秋季收割麦子时，为了节省体力，农夫会每收割一部分麦子就堆放在一堆，然后将堆放的麦子两两合并，以此类推，最后合成一堆再运回仓库。 合并规则是：每次只能将两堆麦子合成一堆，合并麦堆时需要消耗的体力是两个麦堆的重量之和，不考虑麦堆的距离因素。 现给出麦子的堆数和每堆麦子的重量，编程计算出把麦子合成一堆，所需要的最少体力是多少？

输入

二行，第一行是一个整数n（1<n<1000)，为要合并的麦子堆的数量；第二行是n个整数，为每堆麦子的重量，两数之间以空格分隔。

输出

一行，一个整数，为合并麦子成一堆要消耗的最少体力。

样例输入

10

1 4 3 2 9 7 18 22  23 3

样例输出

258