You are given a sequence of ~N~ piles. The ~i~-th pile contains ~a_i~ stones.

In one move, you may merge two adjacent groups of piles into one larger group. The cost of the move is the total number of stones in the newly merged group.

After exactly ~N - 1~ moves, all piles will be merged into one group. Find the minimum possible total cost.

Input

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

The second line contains ~N~ integers: ~a_1, a_2, \ldots, a_N~.

Output

Print one integer: the minimum possible total cost to merge all piles into one group.

Constraints

• ~1 \le N \le 250~
• ~1 \le a_i \le 10^6~

Example 1

Input

4
10 20 30 40

Output

190

Explanation

One optimal sequence is:

• Merge piles with ~10~ and ~20~ stones, paying ~30~.
• Merge the new group with the pile containing ~30~ stones, paying ~60~.
• Merge the new group with the pile containing ~40~ stones, paying ~100~.

The total cost is ~30 + 60 + 100 = 190~.

Example 2

Input

5
1 100 1 100 1

Output

507