Merge Stones

There are N piles of stones arranged in a row, numbered 1, 2, 3, …, N.

Each pile has a certain mass, described by an integer. The task is to merge these N piles into a single pile.

Each time, you may only merge two adjacent piles. The cost of merging is the sum of the masses of those two piles. After merging, the new pile is adjacent to the piles that were adjacent to the original two piles. The total cost of merging varies depending on the order of merges.

For example, with 4 piles of masses 1, 3, 5, 2:

• First merge piles 1 and 2 (cost 4), resulting in 4, 5, 2.
• Then merge the first two piles (cost 9), resulting in 9, 2.
• Then merge the last two (cost 11), total cost 4 + 9 + 11 = 24.
• Alternatively, after first step (4, 5, 2), merge piles 2 and 3 (cost 7), resulting in 4, 7, then merge (cost 11), total cost 4 + 7 + 11 = 22.

The problem is to find a method to minimize the total merging cost, and output the minimum cost.

Input Format

The first line contains an integer N, the number of stone piles.

The second line contains N integers, representing the mass of each pile (each mass ≤ 1000).

Output Format

Output an integer, the minimum cost.

Constraints

1 ≤ N ≤ 300

Sample Input

4
1 3 5 2

Sample Output

22