题目描述

有 (n) 堆果子，每次合并两堆，代价为两堆重量之和。求把所有果子合并成一堆的最小代价。

输入格式

第一行一个整数 (n) ((1 \le n \le 100))，表示果子堆数。
第二行 (n) 个整数 (a_i) ((1 \le a_i \le 10000))，表示每堆果子的重量。

输出格式

一行一个整数，表示最小总代价。

样例

样例输入

4
1 2 3 4

样例输出

19

数据范围与提示

• (1 \le n \le 100)
• (1 \le a_i \le 10000)
• 答案在 64 位有符号整数范围内。

样例解释：先合并 1 和 2，代价 3；再合并 3 和 3，代价 6；最后合并 6 和 4，代价 10；总代价 (3+6+10=19)。