你最近学习了打隔膜。
有 $n$ 个怪物，击败第 $i$ 个怪物 $A_i$ 点体力，而击败它之后可以获得 $B_i$ 点体力。任意时刻，体力都不能是负数。
对每个 $k = 1, 2, \cdots, n$，试求出击败 $k$ 个怪物至少需要多少初始体力。
输入格式
第一行一个正整数 $n, m$，表示怪物个数。
接下来的 $n$ 行，每行两个整数 $A_i, B_i$，表示怪物的属性。
输出格式
输出一行 $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 \leq 16$。
子任务 $2$（$27$ 分）：$n \leq 7000$。
子任务 $3$（$68$ 分）：无特殊限制。
对于 $100\%$ 的数据，$1 \leq n \leq 3 \times 10^5$，$1 \leq A_i, B_i \leq 10^9$。
时间限制：$\texttt{2s}$
空间限制：$\texttt{512MB}$