Có \(N\) hủ kẹo dẻo được đặt trên một hàng. Ban đầu, hủ thứ \(i\) có độ ngọt là \(a_i\).

\(Kaninho\) cố gắng kết hợp tất cả các hủ kẹo này thành một hủ kẹo lớn hơn. Anh ấy thực hiện phép toán dưới đây nhiều lần cho đến khi chỉ còn một hủ kẹo duy nhất thì dừng:

• Chọn \(2\) hủ kẹo kề nhau bất kì và kết hợp chúng lại thành một hủ kẹo. Hủ kẹo mới này có độ ngọt là \(x+y\), trong đó \(x,y\) lần lượt là độ ngọt của hai hủ kẹo trước đó. Và việc này tốn chi phí là \(x+y\). Mối quan hệ về vị trí giữa các hủ kẹo vẫn không thay đổi khi ta kết hợp chúng lại với nhau.

Input

• Dòng thứ nhất chứa số nguyên \(N(2\le N\le 400)\)

• Dòng thứ hai chứa \(N\) số nguyên \(a_i(1\le a_i\le 10^9)\).

Output

• In ra chi phí tối thiểu để kết hợp tất cả các hủ kẹo trên thành \(1\) hủ duy nhất.

Example

4
10 20 30 40 

190