Litli D er að undirbúa hnattsiglingu. Áður en lagt er af stað þarf hann samkvæmt áætlun að ljúka $n$ aðgerðum við undirbúning birgða á listanum sínum, en þessar aðgerðir eru í upphafi númeraðar í röð sem $1, 2, \dots, n$.

Látum núverandi magn birgða vera heiltöluna $x$, þar sem $x = 0$ í upphafi. $i$-tu aðgerðinni er lýst með tveimur jákvæðum heiltölum $a_i, b_i$, og þegar sú aðgerð er framkvæmd verða eftirfarandi breytingar í þessari röð:

1. Fyrst er $x$ hækkað um $a_i$ (þ.e. sett er $x \leftarrow x + a_i$);
2. Síðan er stærðin á $x$ athuguð: ef $x > b_i$ á þeim tímapunkti, þá er $x$ minnkað niður í $b_i$ (þ.e. sett er $x \leftarrow \min(x, b_i)$).

Áður en byrjað er að framkvæma aðgerðirnar getur Litli D gert að hámarki eina breytingu á röð listans: valið hvaða eina aðgerð sem er, tekið hana úr og fært hana aftast í rununa, á meðan innbyrðis röð hinna aðgerðanna helst óbreytt (hann getur líka valið að gera enga breytingu).

Eftir að breytingunni er lokið mun Litli D framkvæma allar $n$ aðgerðirnar í nýju röðinni frá upphafi til enda, hverja aðgerð nákvæmlega einu sinni. Litli D vill vita: eftir að allar aðgerðirnar hafa verið framkvæmdar, hvert er mesta mögulega magn birgða $x$?

Inntak

Lesið gögn úr stdin.

Fyrsta línan inniheldur jákvæða heiltölu $n$, sem táknar fjölda aðgerða.

Í næstu $n$ línum inniheldur $i$-ta línan tvær jákvæðar heiltölur $a_i, b_i$, sem lýsa viðföngum $i$-tu aðgerðarinnar.

Úttak

Skrifið í stdout.

Skrifið út eina línu með einni heiltölu, sem táknar hæsta mögulega gildi á birgðamagninu $x$ eftir að allar aðgerðir hafa verið framkvæmdar.

Dæmi

Inntak 1

3
1 100
100 90
1 1

Úttak 1

90

Athugasemd

Með því að færa $2$. aðgerðina aftast í rununa verður framkvæmdaröð aðgerðanna $1, 3, 2$. Eftir að hverri aðgerð lýkur verður gildið á $x$ í röð $1, 1, 90$.

Ef $1$. aðgerðin er færð aftast verður lokagildið $x = 2$; ef röðinni er ekki breytt eða ef $3$. aðgerðin er færð aftast verður lokagildið $x = 1$. Því er hæsta mögulega gildið á $x$ jafnt og $90$.

Dæmi 2

Sjá supply/supply2.in og supply/supply2.ans í möppu keppanda.

Þetta dæmi uppfyllir skorður prófunartilvika $1 \sim 4$.

Dæmi 3

Sjá supply/supply3.in og supply/supply3.ans í möppu keppanda.

Þetta dæmi uppfyllir skorður prófunartilvika $5 \sim 6$.

Dæmi 4

Sjá supply/supply4.in og supply/supply4.ans í möppu keppanda.

Þetta dæmi uppfyllir skorður prófunartilvika $7 \sim 10$.

Skorður

Fyrir öll gögn er tryggt að $1 \le n \le 2 \times 10^5$ og $1 \le a_i, b_i \le 10^9$. Athugið: gögnin tryggja ekki að $a_i \le b_i$.

Þetta verkefni hefur alls $10$ prófunartilvik, hvert þeirra gefur $10$ stig, og hvert prófunartilvik er metið sjálfstætt. Nákvæmar skorður má sjá í töflunni hér að neðan.

Sérstakur eiginleiki A: $b_1 = b_2 = \dots = b_n$.