Giải bài trực tuyến

English

Vietnamese

You have to cut a piece of wood into n smaller pieces, each piece is of length a_i. The pieces must be cut in order exactly a₁, a₂ ... a_n from left to right.

At each step, you may cut a piece into two smaller pieces. The cost for that cut is the length of the piece before cutting.

Different cut order will result in different costs.

For example, you need to cut a wooden stick of length 20 into 4 pieces of length 3, 5, 2 and 10 in order.

When cutting from left to right:

• 20 cuts into 3 and 17, cost 20.
• 17 cuts into 5 and 12, cost 17.
• 12 cuts into 2 and 10, cost 12.

Total cost: 49

When cutting from right to left:

• 20 cuts into 10 and 10, cost 20.
• 10 cuts into 8 and 2, cost 10.
• 8 cuts into 3 and 5, cost 8.

Total cost: 38

Find the minimum cost to cut the initial piece into n given smaller pieces.

Input

Line 1: n (1 ≤ n ≤ 2000)
Line 2: n positive integers a1, a2 ... an, knowing that the length of the wooden bar a1 + a 2 + ... + an ≤ 500000

Output

A single integer which is the smallest cost found.

Example

Input:
4
3 5 2 10

Output:
37