Farmer Johns $N$ Kühe ($1 \le N \le 50{,}000$), nummeriert $1..N$, wollen weglaufen und zum Zirkus. Ihre Hufe verhindern Seiltanz und Trapezschwingen (und der letzte Versuch, eine Kuh aus einer Kanone zu schießen, scheiterte kläglich). Daher üben sie Akrobatik.

Sie sind wenig kreativ und haben nur einen Trick: übereinander stehen und einen vertikalen Stapel gewisser Höhe bilden. Sie suchen die Reihenfolge im Stapel.

Jede Kuh hat Gewicht ($1 \le W_i \le 10{,}000$) und Stärke ($1 \le S_i \le 1{,}000{,}000{,}000$). Ihr Zusammenbruchrisiko ist das Gesamtgewicht aller Kühe darüber (ohne ihr eigenes) minus ihre Stärke; eine stärkere Kuh hat geringeres Risiko. Finde eine Reihenfolge, die das größte Risiko aller Kühe minimiert.

Eingabe

• Zeile 1: eine ganze Zahl $N$.
• Zeilen $2..N+1$: Zeile $i+1$ beschreibt Kuh $i$ mit zwei durch ein Leerzeichen getrennten ganzen Zahlen $W_i$ und $S_i$.

Ausgabe

• Zeile 1: eine ganze Zahl, das größte Risiko aller Kühe in einer beliebigen optimalen Reihenfolge, die das Risiko minimiert.

Beispiele

Eingabe 1

3
10 3
2 5
3 3

Ausgabe 1

2

Hinweis

Stelle die Kuh mit Gewicht 10 nach unten. Sie trägt die anderen beiden, also ist ihr Risiko $2+3-3=2$. Die anderen Kühe haben geringeres Risiko.