AT_past202004_f タスクの消化

现在有 $n$ 个任务。对于第 $i$ 个任务，你可以在第 $a_i$ 天及以后来完成（今天是第 $1$ 天），并在完成后获得 $b_i$ 的积分。 你每天都会选择一个任务并完成它。对于所有满足 $1 \le k \le n$ 的所有整数 $k$，请求出在 $k$ 天后最多可以获得多少积分。 数据保证，无论 $k$ 是多少，在第 $k$ 天的时候，第 $k$ 天之前完成的任务数量总会不小于 $k$ 个。

第一行输入一个正整数 $n$。 接下来 $n$ 行，每行两个正整数 $a_i,b_i$，中间以单个空格隔开。

按照 $k=1,2,...,n$ 的顺序输出第 $k$ 天可获得的积分的最大值。 ### 约束 所有测试点保证： - $1 \le n \le 2 \times 10^5$； - $1 \le a_i \le n$； - $1 \le b_i \le 100$； - 输入的数均为整数。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leq\ N\ \leq\ 2\times10^5 $ - $ 1\ \leq\ A_i\ \leq\ N $ - $ 1\ \leq\ B_i\ \leq\ 100 $ - 入力中のすべての値は整数である。 ### Sample Explanation 1 $ 1 $ 日目に消化できるタスクは $ 1 $ 番目のタスクだけなので、そのタスクを消化し、$ 3 $ ポイントを得ます。$ k=1 $ の場合、これが答えです。 $ 2 $ 日目に消化できるタスクは $ 1 $ 番目から $ 3 $ 番目までのすべてです。 $ k=2 $ の場合、$ 1 $ 日目に $ 1 $ 番目のタスクを消化し、$ 2 $ 日目に $ 3 $ 番目のタスクを消化することで得られる $ 3+4=7 $ ポイントが得られる最大のポイントです。 $ k=3 $ の場合、$ 3 $ 日目までにはすべてのタスクを消化することができるので、答えは $ 3+2+4=9 $ です。