I'll Do It Tomorrow

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.

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.

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.

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.