Time Management

Interview

Time limit1sMemory limit128 MB

Summary

Given each chore's duration and deadline, find the latest start time that lets John finish all chores before their deadlines, or print -1.

Level: Medium4 of 10
Topics: Greedy, Sorting, Intervals, Implementation
Solved: No attempts yet

Problem

Farmer John has decided to manage his time efficiently. He has numbered his $N$ chores ( $1 \le N \le 1000$ ) — such as milking cows, cleaning the barn, and mending fences.

Completing chore $i$ takes $T_i$ units of time ( $1 \le T_i \le 1000$ ), and it must be finished by its deadline $S_i$ ( $1 \le S_i \le 1{,}000{,}000$ ). John starts his day at $t = 0$ , and once he begins a chore he works on nothing else until it is done.

John loves to sleep in. Print the latest time at which he can start working while still finishing every chore by its deadline.

Input

The first line contains the number of chores $N$ .

Each of the next $N$ lines contains $T_i$ and $S_i$ , separated by a space.

Output

Print the latest time at which John can start working. If he cannot finish all chores on time, print $-1$ .

Examples4

Example 1
Input
```
4
3 5
8 14
5 20
1 16
```
Expected output
```
2
```
Example 2
Input
```
1
5 5
```
Expected output
```
0
```
Example 3
Input
```
3
1 10
2 20
3 30
```
Expected output
```
9
```
Example 4
Input
```
2
2 2
3 5
```
Expected output
```
0
```