Bedao Regular Contest 07 - DEADLINE

View as PDF

Submit solution


Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ công việc, công việc thứ ~i~ có thời hạn deadline ~d_i~ và số điểm ~p_i~. Để lấy được số điểm ~p_i~, bạn phải hoàn thành công việc thứ ~i~ ở thời điểm không trễ hơn deadline ~d_i~.

Hãy tìm cách lấy số điểm lớn nhất nếu thực hiện ~k~ công việc đầu tiên với mọi ~k~ từ ~1~ đến ~N~.

Chú ý: Coi thời điểm bắt đầu thực hiện các công việc là thời điểm ~0~ và thời gian hoàn thành mỗi công việc đều là ~1~ đơn vị thời gian.

Input

  • Dòng đầu tiên chứa số ~N~ (~N \le 10^5~).
  • ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên là ~d_i~ và ~p_i~ cách nhau bởi một dấu cách. (~1 \le d_i, p_i \le 10^6~)

Output

  • Ghi ra ~N~ dòng, dòng thứ ~i~ là số điểm lớn nhất có thể lấy được nếu thực hiện ~i~ công việc đầu tiên.

Sample Input

4
4 20
1 10
1 40
1 30

Sample Output

20
30
60
60

Subtask

  • ~20\%~ số test có ~N \le 10~
  • ~20\%~ số test tiếp theo có ~N \le 1000~
  • ~60\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.