F - タスクの消化 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 7 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 個のタスクがあります。i 個目のタスクは A_i 日目 (今日を 1 日目とします) またはそれ以降に実行することができ、消化することで B_i ポイントが得られます。

あなたは、これから 1 日ごとに、「タスクを一つ選んでそれを消化する」という行為を繰り返します。 1 以上 N 以下のすべての整数 k に対して、これから k 日間で得られるポイントの合計の最大値を求めてください。

ただし、1 以上 N 以下のすべての整数 k に対して、k 日目までに実行することのできるタスクが k 個以上存在することが保証されています。

制約

  • 1 \leq N \leq 2\times10^5
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq 100
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
:
A_N B_N

出力

以下の形式で N 行出力せよ。ここで、ans_k はこれから k 日間で得られるポイントの合計の最大値である。

ans_1
ans_2
:
ans_N

入力例 1

3
1 3
2 2
2 4

出力例 1

3
7
9

1 日目に消化できるタスクは 1 番目のタスクだけなので、そのタスクを消化し、3 ポイントを得ます。k=1 の場合、これが答えです。 2 日目に消化できるタスクは 1 番目から 3 番目までのすべてです。 k=2 の場合、1 日目に 1 番目のタスクを消化し、2 日目に 3 番目のタスクを消化することで得られる 3+4=7 ポイントが得られる最大のポイントです。 k=3 の場合、3 日目までにはすべてのタスクを消化することができるので、答えは 3+2+4=9 です。

入力例 2

5
5 3
4 1
3 4
2 1
1 5

出力例 2

5
6
10
11
14

入力例 3

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

出力例 3

8
17
23
25
26
27

Score : 7 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N tasks. Let today be Day 1. You can do the i-th task on or after Day A_i, and finishing the task gives you B_i points.

Each day, starting with today, you choose one task and finish it. For each integer k from 1 through N, find the maximum total number of points that can be earned in the k days starting with today.

It is guaranteed that there are at least k tasks that you can do in the first k days for each integer k from 1 through N.

Constraints

  • 1 \leq N \leq 2\times10^5
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print N lines in the format below, where ans_k is the maximum total number of points earned on the k days starting with today.

ans_1
ans_2
:
ans_N

Sample Input 1

3
1 3
2 2
2 4

Sample Output 1

3
7
9

On Day 1, only the first task is available. You do that task and earn 3 points, which is the answer for k=1. On Day 2, all three tasks are available. For k=2, do the first task on Day 1 and the third task on Day 2 to earn the maximum number of points: 3+4=7. For k=3, you can finish all the tasks in three days, so the answer is 3+2+4=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