Contest Duration: - (local time) (100 minutes) Back to Home
G - Max (Sum - Max) /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 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