$N$ krów Farmer John ($1 \le N \le 50{,}000$), o numerach $1..N$, chce uciec do cyrku. Kopyta nie pozwalają im chodzić po linie i huśtać się na trapezie (a ostatnia próba wystrzelenia krowy z armaty skończyła się porażką). Postanowiły ćwiczyć akrobatykę.

Nie są zbyt pomysłowe i wymyśliły tylko jeden trik: stać jedna na drugiej, tworząc pionowy stos pewnej wysokości. Wybierają kolejność w stosie.

Każda krowa ma wagę ($1 \le W_i \le 10{,}000$) i siłę ($1 \le S_i \le 1{,}000{,}000{,}000$). Ryzyko upadku to suma wag krów nad nią (bez własnej) minus jej siła, więc silniejsza ma mniejsze ryzyko. Znajdź kolejność minimalizującą największe ryzyko wszystkich krów.

Wejście

• Wiersz 1: liczba całkowita $N$.
• Wiersze $2..N+1$: wiersz $i+1$ opisuje krowę $i$ dwiema liczbami całkowitymi oddzielonymi spacją, $W_i$ i $S_i$.

Wyjście

• Wiersz 1: liczba całkowita — największe ryzyko wszystkich krów w dowolnej optymalnej kolejności minimalizującej ryzyko.

Przykład

Wejście 1

3
10 3
2 5
3 3

Wyjście 1

2

Uwagi

Umieść krowę o wadze 10 na dole. Niesie dwie pozostałe, więc jej ryzyko wynosi $2+3-3=2$. Pozostałe krowy mają niższe ryzyko.