1225: 石子归并

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

在一个操场按次序从左到右摆放着n堆石子（n≤l00），现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分，求最小的得分总和。

Input

第1行为石子堆数n； 第2行为每堆的石子数，每两个数之阿用一个空格分隔。

Output

最小的得分总和。

Sample Input Copy 

6
3 4 6 5 4 2

Sample Output Copy 

61

HINT

Calculation Result

样例说明

3 4 6 5 4 2

7 6 5 4 2

13 5 4 2

13 5 6

13 11

24

7+13+6+11+24=61