题目描述

给定两个长度为 $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)$ 的最大值。

输入格式

第一行一个正整数 $n$。

之后 $n$ 行每行两个正整数 $a_i,b_i$。

输出格式

输出共 $n$ 行。

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

输入输出样例 #1

输入 #1

6
1 1
1 9
4 1
5 9
1 8
4 10

输出 #1

3
4
3
4
5
6

说明/提示

【数据范围】

对于 $20\%$ 的数据，保证 $1 \le n \le 10$。

对于 $40\%$ 的数据，保证 $1 \le n \le 80$。

对于 $60\%$ 的数据，保证 $1 \le n \le 400$。

对于 $80\%$ 的数据，保证 $1 \le n \le 3000$。

对于 $100\%$ 的数据，保证 $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}$。