Tý có \(N\) đống đá xếp thành một hàng ngang. Đống thứ i có trọng lượng \(a_i\). Mỗi bước, bạn chọn hai đống đá kề nhau gộp thành một đống. Chi phí gộp bằng tổng trọng lượng hai đống đó. Hãy tìm tổng chi phí nhỏ nhất để gộp tất cả đống đá thành một đống duy nhất.

#

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 500\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^4\)).

Định dạng đầu ra

• In ra chi phí tối thiểu để gộp toàn bộ \(N\) đống sỏi thành 1 đống.

Ví dụ

Input:

4
1 3 5 2

Output:

22

Giải thích: Gộp \((1, 3)\)->4 (chi phí 4), gộp \((5, 2)\)->7 (chi phí 7), gộp \((4, 7)\)->11 (chi phí 11). Tổng = 4 + 7 + 11 = 22.

Ràng buộc & Subtasks