#P16151. [2022国家队训练南京站]game

[2022国家队训练南京站]game

题目描述

你最近学习了打隔膜。

有 nn 个怪物。击败第 ii 个怪物需要消耗 AiA_i 点体力,而击败它之后可以获得 BiB_i 点体力。任意时刻,体力都不能为负数。

对于每个 k=1,2,…,nk=1,2,\ldots,n,请计算:如果要击败恰好 kk 个怪物,至少需要多少初始体力。

输入格式

第一行一个正整数 nn,表示怪物个数。

接下来 nn 行,每行两个整数 Ai,BiA_i,B_i,表示第 ii 个怪物的属性。

输出格式

输出一行 nn 个非负整数,第 ii 个整数表示击败恰好 ii 个怪物所需的最小初始体力。

样例一

输入

4
1 2
3 4
1 1
2 3

输出

1 2 3 4

样例二

输入

8
304 282
773 724
274 481
43 254
813 110
722 107
140 62
351 418

输出

43 43 63 63 63 288 341 1044

数据范围与提示

  • 子任务 11(55 分):n≤16n\le 16。
  • 子任务 22(2727 分):n≤7000n\le 7000。
  • 子任务 33(6868 分):无特殊限制。

对于 100%100\% 的数据:

$$1\le n\le 3\times 10^5,\qquad 1\le A_i,B_i\le 10^9.$$