📖 Bài giảng & lời giải: đây là Bài tập 5 trong bài giảng Bài 27: Quy hoạch động nâng cao trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Một que gỗ dài $L$ cần được cắt tại $m$ vị trí cho trước $p_1, p_2, \ldots, p_m$ (vị trí $p$ cách đầu trái của que $p$ đơn vị độ dài). Mỗi lần chỉ được cắt một khúc tại một điểm, chi phí của lần cắt bằng độ dài khúc đang bị cắt. Thứ tự cắt tuỳ ý. Tìm tổng chi phí nhỏ nhất để cắt tại tất cả $m$ vị trí.

Dữ liệu vào

• Dòng 1: hai số nguyên $L, m$ ($2 \le L \le 10^9$, $1 \le m \le 200$, $m \lt L$).
• Dòng 2: $m$ số nguyên đôi một khác nhau $p_1, p_2, \ldots, p_m$ ($0 \lt p_i \lt L$), không nhất thiết theo thứ tự tăng dần.

Kết quả

In ra tổng chi phí nhỏ nhất.

Sample Input

10 3
2 4 7

Sample Output

20