提示: 欢迎访问OurACM平台。
Problem 1327 Blocks of Stones II

Accept: 500    Submit: 1906
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There are n blocks of stones in a line laying on the ground. Now you are to merge these blocks of stones together with the restriction that you can only merge the neighbouring blocks each time. The score you get for each merging is the number of stones the new blocks has.

Before each merging, you are allowed to swap any neighbouring blocks for any times. You are to calculate the minimal score you will get during the whole process.

Input

There are multiple test cases. For each case, the first line contains a integer n(n<=10000), representing the number of blocks. The second line contains n integers, representing number of stones in each blocks.

Output

For each case, output one line containing a single integer, representing the minimal score. The results are within 32bit integers.

Sample Input

3 2 5 1

Sample Output

11

Source

chenyan

Submit  Back  Status  Discuss