在一个圆形操场的四周摆放$N$堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的$2$堆合并成新的一堆，合并的花费为这相邻两堆之和

试计算出将$N$堆石子合并成$1$堆的最小花费.

输入格式

数据的第$1$行试正整数$N$,$1 \leq N \leq 100$,表示有$N$堆石子.

第$2$行有$N$个数,分别表示每堆石子的个数.

输出格式

输出最小得分

样例

样例输入

4
4 5 9 4

样例输出

43

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$32768\mathrm{KB}$