P11608 [PA 2016] 雨后的蘑菇 2 / Grzyby po deszczu 2

译自 [Potyczki Algorytmiczne 2016](https://sio2.mimuw.edu.pl/c/pa-2016-1/p/) R3 Grzyby po deszczu 2 [A] (GRZ)。

给定长度为 $n$ 的整数数列 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$。 第 $1$ 天早上，第 $i$ 块地上有 $b_i$ 个蘑菇。每天的晚上，第 $i$ 块地上都会长出 $a_i$ 个蘑菇。 采蘑菇只能在早上进行，一次只能在一块地上采集，一次采集的数量没有限制。 对于 $k=1,2,\cdots,n$，求出：如果在前 $k$ 天**每天早上**选择一块地（可以重复选择同一块地）采蘑菇，最多能采多少个蘑菇？

第一行，一个正整数 $n$。 接下来 $n$ 行，每行两个非负整数 $a_i,b_i$。

输出 $n$ 行，第 $i$ 行一个整数，表示 $k=i$ 时的答案。

- $1\le n\le 10^6$； - $0\le a_i\le 10^6$； - $0\le b_i\le 10^{12}$。