103486: [Atcoder]ABC348 G - Max (Sum - Max)

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

问题描述

给你两个长度为 $N$ 的整数序列 $A$ 和 $B$。对于 $k = 1, 2, \ldots, N$，解决以下问题：

• 考虑选择 $k$ 个在 $1$ 到 $N$（含）之间的不同整数。令 $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