Migrated from Lutece 2044 记忆合并

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

子辉将记忆碎片排成一排，$A_1$,$A_2$,$A_3$,...,$A_n$ 数列表示每个碎片的美好程度，进行合并操纵，每次可以把2个相邻的记忆碎片合并成一个新的记忆碎片，新的记忆碎片的美好程度为这两个的和， 合并两个记忆碎片的代价是两个的美好程度之和 例如 对于 1 , 2 , 3 , 4 ，如果合并 2 和 3 则代价为 5 ，数列变为 1 , 5 , 4

现在子辉想知道把这个数列合并成一个，最小代价和是多少

Input

第一行，一个数字 $n$ ( $1 \le n \le 200$ )表示数列的长度 第二行，有 $n$ 个正整数，第 $i$ 个数表示数列中第 $i$ 个元素值 $A_i$ ( $1 \le A_i \le 10000$ )的大小

Output

一行，一个正整数表示最小的代价和

Samples

4
1 2 3 4

10

Note

样例解释

1.合并1和2 , 代价为 3 , 数列变为 3 3 4

2.合并3和3 , 代价为 6 , 数列变为 6 4

3.合并4和6 , 代价为 10 , 数列变为 10

Resources

2018 UESTC Training for Dynamic Programming