Problem A
Automatic Light

A company has an automatic light at the front door. When an employee enters the building the light lights up immediately and stays on for the next $x$ minutes. If the light is already on, it remains on and reprograms itself to stay on for the next $x$ minutes. Notice that when an employee leaves the building, the light isn’t affected.

You have the list of times when each employee will enter or leave the building and want to configure the light with a new value $x$ in order to save energy.

Find the smallest number $x$ that will leave no employees in the dark, that is, while there is someone at the company, the lights won’t go out.

Input

The first line of input will consist of one integer $n$ ($1 \leq n \leq 10^3$), the number of employees.

$n$ lines will follow. The $i$-th line will contain two integers, $t_{in}$ and $t_{out}$ ($0 \leq t_{in} < t_{out} \leq 40\, 000$), the time, in minutes, that the $i$-th employee enters and leaves the building, respectively.

Each employee will already be in the building at the start of minute $t_{in}$ and will already be outside at the start of minute $t_{out}$, that is, the light needs to be on at minute $t_{in}$, but not necessarily at minute $t_{out}$.

Output

Print a single integer, the smallest value $x$ that will leave no employees in the dark.

1
5 278

273

4
0 10
4 6
11 14
12 15

6