Ghép đá

Ở công trường đá, $n$ đống đá được xếp thành một hàng dọc theo con đường; đống thứ $i$ (tính từ trái sang) nặng $a_i$ tấn. Đội xe cần dồn tất cả về thành một đống duy nhất.

Mỗi lần, đội chọn hai đống đứng cạnh nhau trong hàng hiện tại và dồn chúng thành một đống mới, đặt đúng vào chỗ của hai đống cũ (thứ tự các đống khác không đổi). Chi phí của lần dồn này bằng tổng khối lượng của hai đống. Sau $n-1$ lần dồn, chỉ còn lại một đống.

Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất để dồn tất cả các đống đá thành một đống.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

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

Ràng buộc

• $1\le n\le 400$.
• $1\le a_i\le {10}^9$.

Subtasks

• Subtask 1 ($40\%$ số điểm): $n\le 10$.
• Subtask 2 ($60\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ