Mały D przygotowuje się do podróży dookoła świata. Przed wyjazdem musi zgodnie z planem wykonać $n$ operacji przygotowania zapasów ze swojej listy, które początkowo są ponumerowane kolejno jako $1, 2, \dots, n$.

Oznaczmy aktualną ilość zapasów jako liczbę całkowitą $x$, przy czym początkowo $x = 0$. $i$-ta operacja jest opisana przez dwie dodatnie liczby całkowite $a_i, b_i$, a podczas jej wykonywania następują kolejno poniższe zmiany:

1. Najpierw zwiększamy $x$ o $a_i$ (czyli podstawiamy $x \leftarrow x + a_i$);
2. Następnie sprawdzamy wartość $x$: jeśli w tym momencie $x > b_i$, to zmniejszamy $x$ do $b_i$ (czyli podstawiamy $x \leftarrow \min(x, b_i)$).

Przed rozpoczęciem wykonywania operacji Mały D może dokonać co najwyżej jednej zmiany w kolejności listy: wybrać dowolną jedną operację, wyjąć ją i przenieść na koniec ciągu, podczas gdy względna kolejność pozostałych operacji pozostaje bez zmian (może również zdecydować się na brak jakichkolwiek zmian).

Po zakończeniu zmiany Mały D wykona kolejno wszystkie $n$ operacji od początku do końca zgodnie z nowym porządkiem, każdą operację dokładnie jeden raz. Mały D chciałby wiedzieć, jaka jest maksymalna możliwa ilość zapasów $x$ po wykonaniu wszystkich operacji.

Wejście

Dane należy wczytać ze stdin.

Pierwszy wiersz zawiera jedną dodatnią liczbę całkowitą $n$, oznaczającą liczbę operacji.

Kolejne $n$ wierszy zawiera opis operacji: $i$-ty z nich zawiera dwie dodatnie liczby całkowite $a_i, b_i$, opisujące parametry $i$-tej operacji.

Wyjście

Wynik należy wypisać na stdout.

Wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą maksymalną możliwą wartość ilości zapasów $x$ po wykonaniu wszystkich operacji.

Przykład

Wejście 1

3
1 100
100 90
1 1

Wyjście 1

90

Uwagi

Przenosząc $2$-gą operację na koniec ciągu, kolejność wykonywania operacji zmienia się na $1, 3, 2$. Po wykonaniu każdej kolejnej operacji wartość $x$ wynosi odpowiednio $1, 1, 90$.

Jeśli przeniesiemy $1$-szą operację na koniec, ostatecznie otrzymamy $x = 2$; jeśli nie zmienimy kolejności lub przeniesiemy $3$-cią operację na koniec, ostatecznie otrzymamy $x = 1$. Zatem maksymalna możliwa wartość $x$ wynosi $90$.

Przykład 2

Zobacz pliki supply/supply2.in oraz supply/supply2.ans w katalogu zawodnika.

Ten przykład spełnia ograniczenia dla testów $1 \sim 4$.

Przykład 3

Zobacz pliki supply/supply3.in oraz supply/supply3.ans w katalogu zawodnika.

Ten przykład spełnia ograniczenia dla testów $5 \sim 6$.

Przykład 4

Zobacz pliki supply/supply4.in oraz supply/supply4.ans w katalogu zawodnika.

Ten przykład spełnia ograniczenia dla testów $7 \sim 10$.

Ograniczenia

Dla wszystkich danych gwarantowane jest, że $1 \le n \le 2 \times 10^5$ oraz $1 \le a_i, b_i \le 10^9$. Uwaga: dane nie gwarantują, że $a_i \le b_i$.

Zadanie składa się łącznie z $10$ testów, z których każdy jest wart $10$ punktów, a każdy test jest oceniany niezależnie. Szczegółowe ograniczenia przedstawiono w poniższej tabeli.

Własność specjalna A: $b_1 = b_2 = \dots = b_n$.