题目背景

译自 Potyczki Algorytmiczne 2016 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$ 时的答案。

3
5 10
16 0
5 10

10
26
57

提示

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