Bài tập: Cắt thép

Người ta cần cắt một đoạn thép dài l mét tại n vị trí, mỗi vị trí có toạ độ là một số nguyên tính theo khoảng cách bắt đầu từ đầu đoạn thép. Chi phí để cắt là chiều dài của đoạn cần cắt.

Yêu cầu: Hãy tìm chi phí nhỏ nhất để cắt đoạn thép.

Dữ liệu vào: cho trong file văn bản catthep.inp có cấu trúc như sau:

• Dòng đầu ghi 2 số nguyên dương l và n.
• Dòng thứ 2 ghi n số là toạ độ của các vị trí cần cắt, các toạ độ có giá trị lớn hơn 0 và nhỏ hơn l.

Kết quả: ghi ra file văn bản catthep.out chỉ 1 số là kết quả tìm được

Ví dụ:

catthep.inp	catthep.out
100 3 25 50 75	200

Giải thích:

• Ban đầu cắt đoạn thép tại vị trí 50: chi phí là 100
• Lần thứ hai cắt đoạn thép tại vị trí 25: chi phí là 50
• Lần thứ ba cắt đoạn thép tại vị trí 75: chi phí là 50

       Tổng chi phí là 200

Giới hạn:

• 50% số test có n ≤ 10 và l ≤ 100
• 50% số test còn lại có n ≤ 100 và l ≤ 1000