Problem A
Luz automática

Uma empresa tem uma lâmpada automática na porta de entrada. Sempre que alguém entra na empresa a lâmpada acende imediatamente e fica acesa nos próximos $x$ minutos. Se a lâmpada já estava acesa, ela continua acesa e se reprograma para apagar em $x$ minutos. Note que quando alguém sai da empresa, a lâmpada não é afetada.

Você tem uma lista dos horários de entrada e saída de todos os funcionários da empresa e quer configurar a lâmpada com um novo $x$ para economizar energia.

Encontre o menor $x$ que não deixa nenhum funcionário no escuro, ou seja, que não deixa a lâmpada apagar se algum funcionário estiver na empresa.

Input

A primeira linha do input contém um inteiro $n$ ($1 \leq n \leq 10^3$), o número de funcionários da empresa.

Seguirão $n$ linhas. A $i$-ésima linha contém dois inteiros, $t_{in}$ e $t_{out}$ ($0 \leq t_{in} < t_{out} \leq 40\, 000$), o tempo de entrada e saída do $i$-ésimo funcionário em minutos, respectivamente.

Cada funcionário já entrou na empresa no início do minuto $t_{in}$ e já saiu no início do minuto $t_{out}$, ou seja, a lâmpada precisa estar acesa em $t_{in}$ mas não necessariamente em $t_{out}$.

Output

Imprima um único inteiro, o menor $x$ que não deixa nenhum funcionário no escuro.

1
5 278

273

4
0 10
4 6
11 14
12 15

6