Farmer John 的 $N$ 头奶牛（$1 \le N \le 50{,}000$，编号 $1..N$）计划逃跑加入马戏团。牛蹄使她们无法走钢丝或荡空中秋千（上次试图用大炮发射奶牛也惨败了），于是决定练习杂技。

奶牛们缺乏创意，只想出一种杂技：互相站在背上，叠成一定高度的竖直牛堆。她们正在考虑堆叠顺序。

每头奶牛有重量（$1 \le W_i \le 10{,}000$）和力量（$1 \le S_i \le 1{,}000{,}000{,}000$）。她倒下的风险等于上方所有奶牛的总重量（当然不含自身）减去她的力量（因此越强风险越低）。请确定一种顺序，使所有奶牛中最大的倒下风险最小。

输入格式

• 第 1 行：整数 $N$。
• 第 $2..N+1$ 行：第 $i+1$ 行用两个以空格分隔的整数 $W_i$ 和 $S_i$ 描述奶牛 $i$。

输出格式

• 第 1 行：一个整数，表示任意使风险最小的最优顺序中所有奶牛的最大风险。

样例

输入格式 1

3
10 3
2 5
3 3

输出格式 1

2

说明

把重量 10 的奶牛放在底部。她托着另外两头，倒下风险为 $2+3-3=2$。其他奶牛倒下的风险更低。