Farmer John's N cows (numbered 1..N) plan to escape and join the circus, so they decide to practice performing acrobatics.

The cows are not very creative and have come up with only one acrobatic performance:

Stacking themselves vertically, one on top of the other, to form a tall stack.

The cows are trying to figure out the order in which they should position themselves in this stack.

Each of the N cows has its own weight W_i and its own strength S_i.

The likelihood that a cow cannot withstand the load depends on the total weight of all cows above it (not including itself) minus its body strength. This value is now referred to as the risk value. The larger the risk value, the higher the chance that the cow cannot hold on.

Your task is to determine the order of the cows such that the maximum risk value among all cows is minimized as much as possible.

Input format

The first line contains the integer N, indicating the number of cows.

The next N lines each contain two integers, representing the weight and strength of a cow. The i-th line represents the weight W_i and strength S_i of the i-th cow.

Output format

Output a single integer, representing the minimum possible value of the maximum risk value.

Data range

1 ≤ N ≤ 50000
1 ≤ W_i ≤ 10,000
1 ≤ S_i ≤ 1,000,000,000

Sample input:

3
10 3
2 5
3 3

Sample output:

2