Problem Description

There are $ N $ tasks. The $ i $th task can be performed on or after day $ A_i $ (where today is day 1) and yields $ B_i $ points upon completion.

You will repeat the act of "choosing one task and completing it" day by day. For every integer $ k $ from 1 to $ N $, find the maximum total points that can be obtained in the next $ k $ days.

It is guaranteed that for every integer $ k $ from 1 to $ N $, there are at least $ k $ tasks that can be performed by day $ k $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $

Output Format

Output $ N $ lines in the following format, where $ ans_k $ is the maximum total points that can be obtained in the next $ k $ days.

$ ans_1 $ $ ans_2 $ : $ ans_N $

Sample Input and Output

Sample Input #1

3
1 3
2 2
2 4

Sample Output #1

3
7
9

Sample Input #2

5
5 3
4 1
3 4
2 1
1 5

Sample Output #2

5
6
10
11
14

Sample Input #3

6
1 8
1 6
2 9
3 1
3 2
4 1

Sample Output #3

8
17
23
25
26
27

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq 100$
• All values in the input are integers.

Sample Explanation 1

On day 1, only the 1st task can be completed, so complete it to gain 3 points. For $ k=1 $, this is the answer. On day 2, all tasks from 1st to 3rd can be completed. For $ k=2 $, completing the 1st task on day 1 and the 3rd task on day 2 yields the maximum points of $ 3+4=7 $. For $ k=3 $, since all tasks can be completed by day 3, the answer is $ 3+2+4=9 $.

见题面 Input 部分

见题面 Output 部分