Chi phí ghép kế hoạch phân đoạn

Bối cảnh và bài toán

Một thanh dài x cần được chia thành n đoạn có độ dài đã biết. Mỗi lần cắt một thanh hiện tại thành hai phần, chi phí bằng độ dài thanh bị cắt. Có thể nhìn ngược quá trình: bắt đầu từ các đoạn cuối cùng và ghép hai đoạn thành một; mỗi lần ghép cũng trả chi phí bằng tổng độ dài.

Yêu cầu

Tìm tổng chi phí nhỏ nhất.

Input

• Dòng 1: x n.
• Dòng 2: n độ dài d[i], tổng đúng bằng x.

Output

In chi phí nhỏ nhất.

Ràng buộc

• 1 <= x <= 10^9
• 1 <= n <= 2 * 10^5
• sum d[i] = x

Chấm điểm

Ví dụ 1

Input

8 3
2 3 3

Output

13

Giải thích. Ghép 2+3=5 tốn5, rồi5+3=8 tốn8, tổng13.

Ví dụ 2

Input

10 1
10

Output

0

Giải thích. Đã có đúng một đoạn nên không cần thao tác.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Stick Divisions (Task 1161).

Tham khảo: https://cses.fi/problemset/task/1161