Lille D forbereder en jordomseiling. Før avreise må han etter planen fullføre $n$ operasjoner for forberedelse av forsyninger på listen sin, som i utgangspunktet er nummerert i rekkefølge som $1, 2, \dots, n$.

La den nåværende mengden forsyninger være et heltall $x$, der $x = 0$ til å begynne med. Den $i$-te operasjonen beskrives av to positive heltall $a_i, b_i$, og når denne operasjonen utføres, skjer følgende endringer etter tur:

1. Først økes $x$ med $a_i$ (det vil si sett $x \leftarrow x + a_i$);
2. Deretter sjekkes størrelsen på $x$: hvis $x > b_i$ på dette tidspunktet, reduseres $x$ til $b_i$ (det vil si sett $x \leftarrow \min(x, b_i)$).

Før utførelsen av operasjonene starter, kan Lille D gjøre høyst én justering av rekkefølgen på listen: velge en hvilken som helst operasjon, ta den ut og flytte den til slutten av følgen, mens den relative rekkefølgen til de øvrige operasjonene forblir uendret (han kan også velge å ikke gjøre noen justering i det hele tatt).

Når justeringen er ferdig, vil Lille D utføre alle de $n$ operasjonene etter tur fra start til slutt i den nye rekkefølgen, der hver operasjon utføres nøyaktig én gang. Lille D vil vite hva som er den største mulige mengden forsyninger $x$ etter at alle operasjonene er utført.

Inndata

Les data fra stdin.

Den første linjen inneholder et positivt heltall $n$, som angir antallet operasjoner.

De neste $n$ linjene inneholder på den $i$-te linjen to positive heltall $a_i, b_i$, som beskriver parametrene til den $i$-te operasjonen.

Utdata

Skriv til stdout.

Skriv ut én linje med ett heltall, som angir den største mulige verdien for mengden forsyninger $x$ etter at alle operasjonene er utført.

Eksempler

Inndata 1

3
1 100
100 90
1 1

Utdata 1

90

Forklaring

Hvis den $2$. operasjonen flyttes til slutten av følgen, blir utførelsesrekkefølgen for operasjonene $1, 3, 2$. Etter at hver operasjon er utført, blir verdien av $x$ etter tur $1, 1, 90$.

Hvis den $1$. operasjonen flyttes til slutten, blir sluttverdien $x = 2$; hvis rekkefølgen ikke justeres eller den $3$. operasjonen flyttes til slutten, blir sluttverdien $x = 1$. Derfor er den største mulige verdien av $x$ lik $90$.

Eksempel 2

Se supply/supply2.in og supply/supply2.ans i deltakerens katalog.

Dette eksempelet oppfyller betingelsene for testtilfellene $1 \sim 4$.

Eksempel 3

Se supply/supply3.in og supply/supply3.ans i deltakerens katalog.

Dette eksempelet oppfyller betingelsene for testtilfellene $5 \sim 6$.

Eksempel 4

Se supply/supply4.in og supply/supply4.ans i deltakerens katalog.

Dette eksempelet oppfyller betingelsene for testtilfellene $7 \sim 10$.

Begrensninger

For alle data garanteres det at $1 \le n \le 2 \times 10^5$ og $1 \le a_i, b_i \le 10^9$. Merk: dataene garanterer ikke at $a_i \le b_i$.

Denne oppgaven har totalt $10$ testtilfeller, hvert verdt $10$ poeng, og hvert testtilfelle vurderes uavhengig. Detaljerte begrensninger vises i tabellen nedenfor.

Spesiell egenskap A: $b_1 = b_2 = \dots = b_n$.