[AdditionalFile5197.zip](file://AdditionalFile5197.zip?type=additional_file)

#5197. 「PA 2016」Grzyby po deszczu 2

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2016 Runda 3 Grzyby po deszczu 2

拜托森林再次下起了倾盆大雨。众所周知，雨后蘑菇生长得非常快。Bajtazar，一位热情的蘑菇采集者，绝不能错过这样的机会。他决定外出采集尽可能多的蘑菇。然而，这次他不打算沿路径步行。他带了一架无人机，白天可以飞到任意一块空地并采集那里的所有蘑菇，这一过程恰好需要一天。

自从我们上次见到 Bajtazar 以来，情况有些变化，森林中出现了一种新品种的蘑菇——线性平菇（Agaricus linearis）。这种蘑菇得名于其特性：每晚在同一块空地上新长出的蘑菇数量是固定的。

森林中有 $n$ 块空地。在 Bajtazar 到达的那天，第 $i$ 块空地上有 $b_{i}$ 个蘑菇，并且每晚会新增 $a_{i}$ 个蘑菇。在接下来的 $k$ 天内，我们的主人公将每天派遣无人机到选定的空地（可能是之前已采集过的空地）。请帮助 Bajtazar 确定他能采集到的最大蘑菇数量。由于 Bajtazar 尚未决定采蘑菇的天数，你的任务是为 $[1, n]$ 范围内的每个 $k$ 计算相应的最大蘑菇数量。

输入格式

输入数据的第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示拜托森林中的空地数量。

接下来的 $n$ 行描述空地。第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(0 \leq a_{i} \leq 1000000, 0 \leq b_{i} \leq 10^{12})$，分别表示每晚新增的蘑菇数量和第 $i$ 块空地初始的蘑菇数量。

输出格式

在标准输出中输出 $n$ 行。第 $k$ 行应包含一个数字，表示 Bajtazar 在最优利用无人机的情况下，若采蘑菇持续恰好 $k$ 天，能采集到的蘑菇数量。

样例

输入

3
5 10
16 0
5 10

输出

10
26
57