G - Max (Sum - Max) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 650 点

問題文

長さ 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 としてあり得る値の最大値を求めよ。

制約

  • 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}

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

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

入力例 1

3
4 1
5 6
3 2

出力例 1

3
5
6

以下の選び方がそれぞれ最適です。

  • k = 1 : S = \{1\}
  • k = 2 : S = \{1, 3\}
  • k = 3 : S = \{1, 2, 3\}

入力例 2

2
0 1
0 1

出力例 2

-1
-1

入力例 3

6
9 7
2 4
7 1
-1000 0
3 4
8 5

出力例 3

6
10
17
20
22
-978

Score: 650 points

Problem Statement

You are given two integer sequences A and B of length N. For k = 1, 2, \ldots, N, solve the following problem:

  • Consider choosing k distinct integers between 1 and N, inclusive. Let S be the set of chosen integers. Find the maximum value of \displaystyle (\sum_{i \in S} A_i) - \max_{i \in S} B_i.

Constraints

  • 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}

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print N lines. The i-th line should contain the answer to the problem for k=i.

Sample Input 1

3
4 1
5 6
3 2

Sample Output 1

3
5
6

The following choices are optimal.

  • k = 1: S = \{1\}
  • k = 2: S = \{1, 3\}
  • k = 3: S = \{1, 2, 3\}

Sample Input 2

2
0 1
0 1

Sample Output 2

-1
-1

Sample Input 3

6
9 7
2 4
7 1
-1000 0
3 4
8 5

Sample Output 3

6
10
17
20
22
-978