Trang trại của nông dân John vừa mới nhận được một lượng công việc khổng lồ! Có thể tưởng tượng rằng, ngày làm việc của John bắt đầu từ thời điểm và kết thúc tại thời điểm , được chia thành từng đơn vị thời gian. công việc đã được gửi đến, công việc thứ có hạn chót là và nếu hoàn thành công việc đúng hạn, John sẽ được khoản tiền là . Mỗi công việc cần đúng đơn vị thời gian để hoàn thành, và John phải làm liên tục trong đơn vị đó từ đầu đến cuối.
Do lượng công việc quá lớn, nên anh có thể bỏ qua một số công việc nào đó. Hãy giúp John lựa chọn các công việc sao cho tổng lợi nhuận thu về là nhiều nhất.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên là số lượng công việc;
dòng sau, mỗi dòng chứa hai số nguyên và mô tả hạn chót và lợi nhuận thu được nếu hoàn thành công việc này đúng hạn (không quá thời điểm ).
Dữ liệu ra:
In ra lợi nhuận tối ưu có thể thu được.
Ví dụ:
Dữ liệu vào:
3
2 10
1 5
1 7
Dữ liệu ra:
17
Giải thích:
John không thể hoàn thành được cả công việc, nên anh sẽ chọn làm công việc rồi đến công việc . Tổng lợi nhuận sẽ là .
