Cho một giá trị nguyên dương ban đầu và công việc cần xử lý. Mỗi công việc () được đặc trưng bởi hai thông số:
- : Thời hạn (deadline) để hoàn thành công việc.
- : Chi phí phạt nếu công việc không được hoàn thành đúng hạn.
Quy tắc thực hiện:
- Mỗi công việc tiêu tốn đúng đơn vị thời gian để hoàn thành.
- Tại mỗi đơn vị thời gian, chỉ có thể thực hiện tối đa một công việc.
- Công việc được coi là hoàn thành đúng hạn nếu nó được bắt đầu và kết thúc tại một thời điểm sao cho .
- Với mỗi công việc không hoàn thành đúng hạn, giá trị sẽ bị trừ đi một lượng tương ứng .
Yêu cầu: Hãy tìm cách sắp xếp thứ tự thực hiện các công việc sao cho giá trị còn lại sau khi trừ các khoản phạt là lớn nhất.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương ( là số tiền ban đầu).
- Dòng thứ hai chứa số nguyên dương ( là số lượng công việc).
- Dòng thứ ba gồm số nguyên biểu thị thời hạn của từng công việc.
- Dòng thứ tư gồm số nguyên biểu thị chi phí phạt của từng công việc.
Kết quả:
- Một số nguyên duy nhất là giá trị lớn nhất có thể đạt được.
Ví dụ:
Dữ liệu:
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
Kết quả:
Giải thích: Ta chọn thực hiện các công việc có mức phạt đúng hạn. Chỉ bỏ lỡ công việc có mức phạt . Tổng phạt tối thiểu là . Giá trị còn lại: .
Giới hạn:
- , .
