有一个古老的石头游戏。在游戏开始时，玩家拾取n（1<=n<=1000）堆石头放在一条线上。玩法是按照以下规则将石头合并成一堆：
在游戏的每一步，玩家可以将两个相邻的两堆石头合并为一堆。分数是新堆石头的数量。
你要写一个程序来确定总分的最小值。

第一行包含一个整数n，表示有几堆石头。
接下来一行n个整数表示游戏开始时每堆石头的数量。

一行一个正整数表示答案。答案不会超过1000000000。

样例二：
输入：
3
3 4 3
输出：
17


样例三：
输入：
4
1 1 1 1
输出：
8
样例四：

输入：
4
2 5 3 1
输出：
22

Garsia-Wachs poj 1738 算法 动态规划 区间