Farmer John's Sleepy Schedule

Farmer John has N jobs to complete, where the i^th job takes T_i units of time and must be finished by time S_i. The constraints are given by: \(1 \le N \le 1000\), \(1 \le T_i \le 1000\) and \(1 \le S_i \le 10^6\). Starting at time \(t = 0\) and working continuously on one job at a time (without pause), determine the latest time that Farmer John can begin working so that all jobs are completed by their deadlines. If it is impossible to finish all jobs on time, output \(-1\).

Hint: One effective strategy is to sort the jobs in ascending order of deadlines and schedule them backwards. For each job (in reverse order), update the latest start time as \(\text{current} = \min(\text{current}, S_i) - T_i\). The final value of \(\text{current}\) is the answer if it is non-negative; otherwise, the answer should be \(-1\).

inputFormat

The first line contains a single integer \(N\), representing the number of jobs.

Each of the following \(N\) lines contains two space-separated integers \(T_i\) and \(S_i\) which denote the time required for the \(i^th</em> job and its deadline, respectively.

Input is read from the standard input.

outputFormat

Output a single integer, representing the latest time Farmer John can start working so that all jobs can be finished on time, or \(-1\) if it is impossible.

Output is written to the standard output.

sample

3
3 10
2 5
1 7

3