Có n công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi đúng 1 giờ chạy máy. Với mỗi việc ta biết thời hạn cuối cùng phải nộp kết quả thực hiện sau khi đã hoàn thành việc đó và tiền thù lao thu được nếu nộp kết quả trước hoặc đúng hạn.

Yêu cầu: Chỉ cho một máy tính, hãy lập lịch để thực hiện đủ n công việc trên máy tính sao cho tổng tiền thu được là lớn nhất với thời gian hoạt động của máy tính là nhỏ nhất.

Giả thiết rằng máy tính được khởi động vào đầu ca (thời điểm t = 0) và chỉ tắt máy sau khi đã hoàn thành đủ n công việc.

Dữ liệu vào: Đọc từ file BAI3.INP có cấu trúc như sau:

- Dòng đầu tiên ghi số n (1 ≤ n ≤ 200)

- n  dòng tiếp theo, dòng thứ i ghi hai số nguyên t_i và m_i tương ứng với thời hạn giao nộp kết quả công việc và số tiền thù lao của việc thứ i (1 ≤ m_i ≤ 10⁶; 1 ≤ t_i ≤ 10⁴).

Dữ liệu ra: Ghi ra file BAI3.OUT gồm n + 1 dòng:

• Trong n dòng đầu tiên, dòng thứ j ghi số tự nhiên i cho biết việc thứ i được làm trong đơn vị thời gian j.
• Dòng cuối cùng ghi tổng số tiền thu được

Ví dụ: