You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC348G] Max (Sum - Max)

题目描述

给定两个长为 $N$ 的序列 $A_{1...N}$ 和 $B_{1...N}$ ，令 $S\in\{1,...,N\}$ 是一个下标集合，且记 $|S|=k$ 。

现在对每个 $k=1,2,...,N$ ，求$\displaystyle\ (\sum_{i\ \in\ S}\ A_i)\ -\ \max_{i\ \in\ S}\ B_i$ 的最大值。

输入格式

第一行一个整数 $N$ ，接下来 $N$ 行每行两个整数 $A_i,B_i$ 。

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

输出格式

$N$ 行，第 $i$ 行表示 $k=i$ 时的答案。

输入输出样例 #1

输入 #1

3
4 1
5 6
3 2

输出 #1

3
5
6

输入输出样例 #2

输入 #2

2
0 1
0 1

输出 #2

-1
-1

输入输出样例 #3

输入 #3

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

输出 #3

6
10
17
20
22
-978

说明/提示

数据范围

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

样例解释 1

以下是对每个 $k$ 选定 $S$ 的方案。

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