As $N$ vacas de Farmer John ($1 \le N \le 50{,}000$), numeradas $1..N$, planejam fugir para o circo. Seus cascos impedem andar na corda bamba e usar o trapézio (e a última tentativa de lançar uma vaca de um canhão foi um fracasso). Decidiram praticar acrobacias.

Elas não são muito criativas e inventaram só um truque: ficar umas sobre as outras em uma pilha vertical de certa altura. Estão escolhendo a ordem na pilha.

Cada vaca tem peso ($1 \le W_i \le 10{,}000$) e força ($1 \le S_i \le 1{,}000{,}000{,}000$). Seu risco de cair é o peso total das vacas acima (sem seu próprio peso) menos sua força, então uma vaca mais forte tem menor risco. Encontre uma ordem que minimize o maior risco de todas.

Entrada

• Linha 1: um inteiro $N$.
• Linhas $2..N+1$: a linha $i+1$ descreve a vaca $i$ por dois inteiros separados por um espaço, $W_i$ e $S_i$.

Saída

• Linha 1: um inteiro, o maior risco entre todas as vacas em qualquer ordem ótima que minimize o risco.

Exemplos

Entrada 1

3
10 3
2 5
3 3

Saída 1

2

Nota

Coloque a vaca de peso 10 embaixo. Ela carrega as outras duas, então seu risco é $2+3-3=2$. As outras têm risco menor.