Có N viên sỏi xếp thành 1 hàng, đống thứ i có ai viên sỏi. Ta có thể ghép hai đống kề nhau thành 1 đống và mất chi phí bằng tổng hai đống sỏi đó.

Hãy tìm cách ghép N đống sỏi này thàng một đống với chi phí nhỏ nhất.

Ví dụ: có 5 đống sỏi lần lượt là (4, 1, 2, 7, 5)

Dữ liệu vào:

- Dòng 1 chứa số nguyên dương n (1 <= n <= 100)

- Dòng 2 chứa n số nguyên dương a₁, a₂, …, a_n (1 <= a_i <= 1000) – là số lượng viên sỏi trong mỗi đống.

Kết quả ra:

- Một dòng duy nhất chứa một số nguyên dương là chi phí nhỏ nhất.