Les $N$ vaches de Farmer John ($1 \le N \le 50{,}000$), numérotées $1..N$, veulent fuir et rejoindre le cirque. Leurs sabots empêchent la marche sur corde et le trapèze (et leur dernier essai de tir d’une vache au canon a lamentablement échoué). Elles vont donc pratiquer l’acrobatie.

Peu créatives, elles n’ont trouvé qu’un numéro : se tenir les unes sur les autres en une pile verticale d’une certaine hauteur. Elles cherchent l’ordre dans cette pile.

Chaque vache a un poids ($1 \le W_i \le 10{,}000$) et une force ($1 \le S_i \le 1{,}000{,}000{,}000$). Son risque d’effondrement est le poids total des vaches au-dessus (sans son propre poids) moins sa force, donc une vache plus forte risque moins. Trouvez un ordre minimisant le risque maximal de toutes les vaches.

Entrée

• Ligne 1 : un entier $N$.
• Lignes $2..N+1$ : la ligne $i+1$ décrit la vache $i$ avec les entiers $W_i$ et $S_i$ séparés par un espace.

Sortie

• Ligne 1 : un entier, le plus grand risque de toutes les vaches dans tout ordre optimal minimisant le risque.

Exemples

Entrée 1

3
10 3
2 5
3 3

Sortie 1

2

Remarque

Placez la vache de poids 10 en bas. Elle porte les deux autres, donc son risque est $2+3-3=2$. Les autres risquent moins.