Chia Mảng Knuth

Cho mảng $n$ số nguyên. Ban đầu cả mảng là một đoạn duy nhất. Mỗi bước, bạn chọn một đoạn và chia nó thành hai đoạn liên tiếp. Chi phí của một lần chia đoạn bằng tổng tất cả các phần tử trong đoạn đó. Mục tiêu là chia mảng thành $n$ đoạn đơn (mỗi đoạn gồm một phần tử) với tổng chi phí nhỏ nhất.

Dữ liệu vào

• Dòng 1: số nguyên $n$.
• Dòng 2: $n$ số nguyên $x_1,x_2,\dots ,x_n$.

Dữ liệu ra

• Một số nguyên: tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le 5000$
• $1\le x_i\le {10}^9$

Ví dụ