你最近学习了打隔膜。
有 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
数据范围与提示
子任务 1(5 分):n≤16。
子任务 2(27 分):n≤7000。
子任务 3(68 分):无特殊限制。
对于 100% 的数据,1≤n≤3×105,1≤Ai,Bi≤109。
时间限制:2s
空间限制:512MB