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