#P14015. [PA 2016] 雨后的蘑菇 2 / Grzyby po deszczu 2

    ID: 13221 传统题 5000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400贪心数据结构平衡树排序模拟队列

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

5s/512M

题目描述

给定长度为 nn 的整数数列 a1,…,ana_1,\ldots,a_n 和 b1,…,bnb_1,\ldots,b_n。

第 11 天早上,第 ii 块地上有 bib_i 个蘑菇。每天的晚上,第 ii 块地上都会长出 aia_i 个蘑菇。

采蘑菇只能在早上进行,一次只能在一块地上采集,一次采集的数量没有限制。

对于 k=1,2,⋯ ,nk=1,2,\cdots,n,求出:如果在前 kk 天每天早上选择一块地(可以重复选择同一块地)采蘑菇,最多能采多少个蘑菇?

输入格式

第一行,一个正整数 nn。

接下来 nn 行,每行两个非负整数 ai,bia_i,b_i。

输出格式

输出 nn 行,第 ii 行一个整数,表示 k=ik=i 时的答案。

输入输出样例 #1

输入 #1

3
5 10
16 0
5 10

输出 #1

10
26
57

说明/提示

  • 1≤n≤1061\le n\le 10^6;
  • 0≤ai≤1060\le a_i\le 10^6;
  • 0≤bi≤10120\le b_i\le 10^{12}。