Description

Farmer John's N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts.

The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack.

Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows.

农场主约翰的 $N(1\le N\le 50,000)$ 头奶牛（编号为 $1...N$）打算逃跑，加入马戏团。

奶牛们的创造力并不强，只想出了一个杂技绝技：互相站在一起，形成一个有一定高度的垂直堆叠。奶牛们正试图找出一种堆叠时的排列顺序。

$N$ 头奶牛有着各自相应的重量 $(1\le W_i\le 10,000)$和体力 $(1\le S_i\le 1,000,000,000)$。一头奶牛倒下的风险等于压在它上面的所有奶牛的总重量（当然不包括它自身的重量）减去它的体力（因此，体力好的奶牛风险较低）。你的任务是确定奶牛的排序，使最危险的一头奶牛的倒塌风险降到最低。

Format

Input

* Line 1: A single line with the integer N.

* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

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

Output

* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

• 输出共 $1$ 行：一个整数，给出所有奶牛在所有最优排序中的最大风险里最小的一个。

Samples

3
10 3
2 5
3 3

2

OUTPUT DETAILS:

Put the cow with weight 10 on the bottom. She will carry the other two cows, so the risk of her collapsing is 2+3-3=2. The other cows have lower risk of collapsing.

样例解释：

将重量为 $10$ 的奶牛放在底部。它将驮起另外两头奶牛，因此它倒下的风险为 $2+3-3=2$。其他奶牛倒下的风险较低。

Limitation

1s, 65536KiB for each test case.