HKBU greedy 练习

D. 大鱼吃小鱼

单点时限: 2.0 sec

内存限制: 256 MB

oxx 玩一个经典的大鱼吃小鱼的游戏。

  • 任意时刻只能吃大小小于等于自己的鱼。
  • 任何时刻都要保证鱼的大小是正整数
  • 当吃了第 $i$ 条鱼之后自己的大小 $x$ 会变为 $x + a_{i}$。

oxx 想知道他初始鱼的大小至少需要多大才能吃完这 $n$ 条鱼。吃的顺序可以任意。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 10^6)$ 表示鱼的条数。

接下去 $n$ 行,每行两个整数 $w_{i}, a_{i}$ $(1 \leq w_{i} \leq 10 ^ 9, -10 ^ 9 \leq a_{i} \leq 10 ^ 9)$,分别表示鱼的大小,和吃完鱼之后会膨胀的差。

输出格式

输出一个整数表示吃完所有鱼的初始大小的最小值。

样例

Input
3
10 2
3 -1
2 5
Output
5

提示

至少需要 5,先吃第三条变为 10,再吃第一条变为 12,最后吃第二条变为 11。