Do It Tomorrow

Memory limit: 128 MB

procrastination (latin procrastinatus, from pro- forward, cras tomorrow)
is the act of putting off important tasks to a later time

Byteasar tends to postpone all the tasks he needs to perform. However, if he promises to do something, you can certainly count on him.

Byteasar woke up early today and prepared a list of tasks that he needs to perform in near future. The -th task will take him consecutive days to perform and has to be completed within the next days, starting from today. Byteasar would like to know how much time he can spend doing nothing until he really has to start performing some tasks. Could you write a program that will help him find that out? Byteasar could also write such a program himself, however this could disturb his procrastination period.

Input

The first line of input contains one integer (): the number of tasks that Byteasar has to perform. The following lines hold a description of the tasks. The -th of those lines contains two integers and (). We assume that Byteasar is able to perform all the tasks on time.

Output

Your program should output one integer : the maximum number of days during which Byteasar can avoid working. In other words, on the day number at latest Byteasar must start performing one of the tasks in order to be able to eventually complete all the tasks on time.

Example

For the input data:

3
2 8
1 13
3 10

the correct result is:

5

Explanation of the example: For the first 5 days Byteasar rests. On the following 5 days he performs the first and the third task (in that order). Afterwards he rests for 1 day and performs the second task, which takes him 2 days.

Task author: Tomasz Idziaszek.