Gộp đá chi phí nhỏ nhất

Cho $N$ đống đá xếp thành một hàng. Đống thứ $i$ chứa $a_i$ viên đá.

Bạn được phép thực hiện thao tác gộp như sau: chọn hai đống nằm kề nhau trong hàng rồi gộp chúng lại thành một đống mới (đống mới chiếm vị trí của hai đống cũ trong hàng, do đó số đống giảm đi $1$). Chi phí của một thao tác gộp bằng tổng số đá của hai đống vừa được gộp.

Bạn cần lặp lại thao tác trên đúng $N-1$ lần để cuối cùng chỉ còn lại một đống duy nhất. Hãy tìm tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

• Dòng $1$: số nguyên $N$.
• Dòng $2$: $N$ số nguyên $a_1,a_2,\dots ,a_N$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng chi phí gộp nhỏ nhất.

Ràng buộc

• $1\le N\le 5000$
• $1\le a_i\le {10}^4$
• Nếu $N=1$, kết quả là $0$ (không cần gộp).
• Đáp số có thể lên tới khoảng $2.5·{10}^{11}$, hãy dùng kiểu số nguyên 64-bit.

Ví dụ

Ghi chú

Chú ý: chỉ được gộp hai đống đang kề nhau trong hàng tại thời điểm hiện tại. Việc gộp tham lam hai đống nhỏ nhất kiểu Huffman (không quan tâm vị trí) sẽ cho kết quả sai vì có thể chọn cặp không kề nhau.