Selling Goods

Interview

Time limit2sMemory limit128 MB

Summary

Given each buyer's max price and delivery cost, choose a sale price (ties broken by lowest) that maximizes total profit summed over buyers who purchase profitably.

Level: Medium4 of 10
Topics: Brute force, Sorting, Greedy, Array
Solved: No attempts yet

Problem

A seller wants to sell one new product for the greatest possible profit. There are N interested buyers. For each buyer i, Ai is the maximum amount they are willing to pay, and Bi is the delivery cost for selling to that buyer.

If the seller sets the price to P, only buyers with Ai at least P are willing to buy. The seller may skip any willing buyer that would not produce profit. Therefore, selling to buyer i contributes P - Bi, and it is useful only when that value is positive.

Given Ai and Bi for all N buyers, find the sale price P that maximizes total profit.

Input

The first line contains N, the number of interested buyers. N is at most 50.

Each of the next N lines contains two nonnegative integers Ai and Bi, separated by a space: the buyer's maximum price and the delivery cost. Both values are at most 10^6, and the delivery cost may be 0.

Output

Print the price that maximizes total profit. If several prices give the same maximum profit, print the lowest such price.

If no price can produce positive profit, print 0.

Examples5

Example 1
Input
```
3
13 0
22 0
35 0
```
Expected output
```
22
```
Example 2
Input
```
3
13 5
22 15
35 30
```
Expected output
```
13
```
Example 3
Input
```
3
13 15
22 30
35 40
```
Expected output
```
0
```
Example 4
Input
```
5
10 1
10 5
20 11
20 15
5 0
```
Expected output
```
10
```

Example 5

Input

Expected output