THỰC HÀNH

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ờ máy. Với mỗi việc ta biết thời hạn phải nộp kết quả thực hiện sau khi hoàn thành việc đó và tiền thưởng thu được nếu nộp kết quả trước hoặc đúng thời điểm quy định. Chỉ có một máy tính trong tay, 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 số tiền thưởng thu được là lớn nhất và thời gian hoạt động của máy là nhỏ nhất. Giả thiết rằng máy đượ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:

• Dòng đầu tiên là số N.
• N dòng tiếp theo, dòng thứ i chứa hai số t_i và p_i là thời hạn giao nộp và tiền thưởng của công việc thứ i. Các số cách nhau bởi dấu cách.

Dữ liệu ra:

Một số nguyên duy nhất là tổng số tiền lớn nhất thu được.

Ví dụ:

Dữ liệu vào:
4
1 15
3 10
5 100
1 27

Dữ liệu ra:
137

Giới hạn: 1 ≤ N ≤ 10⁵;  0 ≤ t_i ≤ 10⁴; 0 ≤ p_i ≤ 10⁵