题目描述

作为一名随从当然很酷，但哥萨克胡子比他们更强大……

哥萨克胡子手下有 $n$ 个随从，编号为 $1$ 到 $n$ 的整数。每个随从由其力量和耐力描述。第 $i$ 个随从的力量为 $a_i$，耐力为 $b_i$。

哥萨克耳朵请求哥萨克胡子将一支随从小队交由他指挥。假设哥萨克耳朵请求移交 $k$ 个随从，那么哥萨克胡子可以将 任意 $k$ 个随从交给他的朋友。这些随从的编号可以是任意的，不一定连续。每个小队必须有一名领袖，由哥萨克胡子指定。

英雄们为每支随从小队定义了其 价值。他们认为，小队的价值等于 领袖的力量 加上 所有其他 随从（如果存在）的耐力之和。小队的 规模 指的是其中随从的数量。

假设有四个随从，其属性如下：

• 力量 $3$，耐力 $6$，
• 力量 $7$，耐力 $3$，
• 力量 $1$，耐力 $8$，
• 力量 $6$，耐力 $5$。

如果哥萨克耳朵请求移交一支由 $3$ 个随从组成的小队，那么哥萨克胡子可以选择例如第一个、第二个和第四个。如果他指定第二个为领袖，那么该小队的价值为 $7$（领袖的力量）$+$ $6$（第一个的耐力）$+$ $5$（第四个的耐力）$= 18$。

设 $f(k)$ 为在所有规模为 $k$ 的小队中，所能达到的 最小 价值。

在前面的例子中，为了最小化价值，哥萨克胡子最好选择包含第二、三、四个随从的小队，并指定第三个随从为领袖。此时小队的价值为 $1 + 3 + 5 = 9$。由于没有更好的方案，因此 $f(3) = 9$。

现在，两位哥萨克想要知道所有可能的 $f$ 值。请帮助他们计算 $f(1), f(2), \ldots, f(n)$ 的值。

输入格式

第一行包含一个整数 $n$ $(1 \le n \le 2 \cdot 10^5)$ —— 哥萨克胡子拥有的随从数量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(1 \le a_i, b_i \le 10^9)$ —— 分别表示编号为 $i$ 的随从的力量和耐力。

输出格式

输出 $n$ 个整数 —— $f(1), f(2), \ldots, f(n)$。

3
1 4
3 3
2 1

1
2
5

5
3 4
3 3
2 4
4 3
5 3

2
5
8
11
15

提示

第一个样例的解释：

为了构成规模为 $1$ 的所有小队中的最小价值，需要构成由编号 $1$ 的随从组成的小队。

为了构成规模为 $2$ 的所有小队中的最小价值，需要构成由编号 $1$ 和 $3$ 的随从组成的小队，并选择编号 $1$ 的随从为领袖。

为了构成规模为 $3$ 的所有小队中的最小价值，需要构成包含所有随从的小队，并选择编号 $1$ 的随从为领袖。

$$\begin{array}{|c|c|c|c|c|} \hline \rule{0pt}{1.5em} \textbf{子任务编号} & \textbf{n} & \textbf{a, b} & \textbf{额外限制} & \textbf{分值} \\ \hline \rule{0pt}{1.5em} 1 & 1 \le n \le 2 \cdot 10^5 & 1 \le a, b \le 3 & - & 7 \\ \hline \rule{0pt}{1.5em} 2 & 1 \le n \le 2000 & 1 \le a, b \le 10^9 & 所有\ a\ 值相等 & 13 \\ \hline \rule{0pt}{1.5em} 3 & 1 \le n \le 2 \cdot 10^5 & 1 \le a, b \le 10^9 & 所有\ a\ 值相等 & 8 \\ \hline \rule{0pt}{1.5em} 4 & 1 \le n \le 100 & 1 \le a, b \le 10^9 & - & 23 \\ \hline \rule{0pt}{1.5em} 5 & 1 \le n \le 2000 & 1 \le a, b \le 10^9 & - & 19 \\ \hline \rule{0pt}{1.5em} 6 & 1 \le n \le 2 \cdot 10^5 & 1 \le a, b \le 2 \cdot 10^5 & - & 17 \\ \hline \rule{0pt}{1.5em} 7 & 1 \le n \le 2 \cdot 10^5 & 1 \le a, b \le 10^9 & - & 13 \\ \hline \end{array}$$