AT_abc348_g [ABC348G] Max (Sum - Max)

[problemUrl]: https://atcoder.jp/contests/abc348/tasks/abc348_g 長さ $ N $ の整数列 $ A,\ B $ が与えられます。$ k\ =\ 1,\ 2,\ \ldots\ ,N $ について、以下の問題を解いてください。 - $ 1 $ 以上 $ N $ 以下の相異なる整数 $ k $ 個を選ぶことを考える。選んだ整数の集合を $ S $ として、 $ \displaystyle\ (\sum_{i\ \in\ S}\ A_i)\ -\ \max_{i\ \in\ S}\ B_i $ としてあり得る値の最大値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

$ N $ 行出力せよ。$ i $ 行目には、 $ k=i $ についての問題の答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ -10^9\ \leq\ A_i\ \leq\ 10^9 $ - $ -2\ \times\ 10^{14}\ \leq\ B_i\ \leq\ 2\ \times\ 10^{14} $ ### Sample Explanation 1 以下の選び方がそれぞれ最適です。 - $ k\ =\ 1 $ : $ S\ =\ \{1\} $ - $ k\ =\ 2 $ : $ S\ =\ \{1,\ 3\} $ - $ k\ =\ 3 $ : $ S\ =\ \{1,\ 2,\ 3\} $