Có ~N~ cục thạch xếp thành một hàng ngang. Ban đầu, cục thạch thứ ~i~, đếm từ trái sang, có kích thước ~a_i~.

Taro cố gắng ghép những cục thạch này lại với nhau để tạo thành một cục thạch lớn hơn. Anh ấy sẽ liên tục lặp lại thao tác sau cho đến khi chỉ còn lại một cục thạch duy nhất:

• Taro chọn hai cục thạch kế bên nhau và ghép chúng lại. Cục thạch mới sẽ có kích thước là ~x+y~, ~x~ và ~y~ là kích thước của hai cục thạch được chọn trước khi được ghép. Chi phí phát sinh là ~x+y~ và vị trí tương đối giữa các cục thạch là không thay đổi trong suốt quá trình kết hợp các cục thạch.

Taro là một người tiết kiệm. Bạn hãy giúp Taro tìm chi phí phát sinh nhỏ nhất có thể.

Input

Dòng đầu tiên chứa số nguyên ~N(2 \leq N \leq 400)~ là số lượng cục thạch.

Dòng thứ hai chứ ~N~ số nguyên ~a_1,a_2,a_3,...,a_n (1 \leq a_i \leq 10^9)~.

Output

Dòng duy nhất là chi phí phát sinh nhỏ nhất.

Sample 1

Input

4
10 20 30 40

Output

190

Taro nên thực hiện như sau (những cục thạch được ghép sẽ được in đậm).

• (10, 20, 30, 40) → (30, 30, 40)
• (30, 30, 40) → (60, 40)
• (60, 40) → (100)

Sample 2

Input

5
10 10 10 10 10

Output

120

Taro có thể thực hiện các thao tác như dưới đây:

• (10, 10, 10, 10, 10) → (20, 10, 10, 10)
• (20, 10, 10, 10) → (20, 20, 10)
• (20, 20, 10) → (20, 30)
• (20, 30) → (50)

Sample 3

Input

3
1000000000 1000000000 1000000000

Output

5000000000

Câu trả lời có thể không vừa kiểu int.

Sample 4

Input

6
7 6 8 6 1 1

Output

68

Taro nên thực hiện các thao tác như sau:

• (7, 6, 8, 6,1, 1) → (7, 6, 8, 6, 2)
• (7, 6, 8, 6, 2) → (7, 6, 8, 8)
• (7, 6, 8, 8) → (13, 8, 8)
• (13, 8, 8) → (13, 16)
• (13, 16) → (29)