最大化(和 − 最大值)

题目描述

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

考虑从 $1$ 到 $N$ 中选出 $k$ 个互不相同的整数。设选出的整数构成的集合为 $S$。求

[ \left(\sum_{i \in S} A_i\right) - \max_{i \in S} B_i ]

的最大值。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

输出 $N$ 行。第 $i$ 行应输出 $k=i$ 时问题的答案。

样例

3
4 1
5 6
3 2

3
5
6

以下选择为最优选择。

$k = 1$: $S = \{1\}$

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

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

2
0 1
0 1

-1
-1

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

6
10
17
20
22
-978

数据范围

• $1 \le N \le 2 \times 10^5$
• $-10^9 \le A_i \le 10^9$
• $-2 \times 10^{14} \le B_i \le 2 \times 10^{14}$