Problem C: 环形石子合并

Problem C: 环形石子合并

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 120  Solved: 34
[Submit] [Status] [Web Board] [Creator:]

Description

有n堆石子按照环形摆放,现在PIPI想要将这些石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。
现在PIPI想知道有没有这样一种方案,可以使得进行n-1次合并后的总得分是所有方案中最少的呢?

Input

第一行包含整数 n,表示共有n堆石子。
第二行包含n个整数m,分别表示每堆石子的数量。
1<=n<=200,1<=m<=1e5

Output

输出有一行,为所有方案中的最小得分。

Sample Input

4
4 5 9 4

Sample Output

43