有一排石子，共$n$ 堆。现要将石子有次序地合并成一堆。

规定每次只能选相邻的$2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将$n$堆石子合并成一堆的最小得分。

输入

第一行为一个正整数$N（2\le N\le 100)$;

以下$N$行，每行一个正整数，小于$10000$，分别表示第i堆石子的个数$（1\le i\le N）$。

输出

一个正整数，即最小得分。

样例

样例输入1

7
13
7
8
16
21
4
18

样例输出1

239