I'll Do It Tomorrow

Interview

Time limit2sMemory limit256 MB

Summary

Given n jobs with lengths and deadlines, find the longest idle prefix of days, counting from day 1, before some work must begin.

Level: Medium7 of 10
Topics: Greedy, Sorting, Binary search, Prefix sum
Solved: No attempts yet

Problem

Ugh, I really don't want to do my assignments. I don't want to do anything at all.

There are $n$ assignments listed on my desk. Each assignment $i$ takes $d_i$ days to finish and must be submitted within $t_i$ days from today. In other words, if today is day 0, assignment $i$ must be completed before the end of day $t_i$ . Once you start an assignment you must work on it continuously until it is done, without any break, and you can work on only one assignment at a time.

Today (day 0) I've decided to do nothing. On top of that, starting from tomorrow I want to keep doing nothing and relax for as long as possible.

Assuming every assignment can be finished by its deadline, find the maximum number of consecutive days, starting from tomorrow (day 1), that I can relax and do nothing.

Input

The first line contains an integer $n$ ( $1 \le n \le 10^6$ ), the number of assignments.

Each of the next $n$ lines contains two integers $d_i$ and $t_i$ ( $1 \le d_i, t_i \le 10^9$ ), separated by a space, describing one assignment. Today is day 0.

It is guaranteed that there always exists a way to finish every assignment on time even if you do nothing today.

Output

Print, on a single line, the maximum number of consecutive days you can relax starting from tomorrow (day 1). For example, if the answer is 0 you must start an assignment tomorrow, and if it is 1 you must start an assignment the day after tomorrow.

Hint

For the first example, you relax on days 1–5, work on the first assignment on days 6–7, the third assignment on days 8–10, relax on days 11–12, and work on the second assignment on day 13.

Examples3

Example 1
Input
```
3
2 8
1 13
3 10
```
Expected output
```
5
```
Example 2
Input
```
1
1 1
```
Expected output
```
0
```
Example 3
Input
```
1
1 100
```
Expected output
```
99
```