QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+2]

# 8362. game

Statistics

你最近学习了打隔膜。

n 个怪物,击败第 i 个怪物 Ai 点体力,而击败它之后可以获得 Bi 点体力。任意时刻,体力都不能是负数。

对每个 k=1,2,,n,试求出击败 k 个怪物至少需要多少初始体力。

输入格式

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

接下来的 n 行,每行两个整数 Ai,Bi,表示怪物的属性。

输出格式

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

样例一

input

4
1 2 3 4
1 1 2 3

output

1 2 3 4

样例二

input

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

output

43 43 63 63 63 288 341 1044

数据范围与提示

  • 子任务 15 分):n16

  • 子任务 227 分):n7000

  • 子任务 368 分):无特殊限制。

对于 100% 的数据,1n3×1051Ai,Bi109

时间限制:2s

空间限制:512MB