Pikku D valmistelee maailmanympärysmatkaa. Ennen lähtöä hänen täytyy suunnitelman mukaisesti suorittaa listalla olevat $n$ tarvikkeiden valmisteluoperaatiota, jotka on aluksi numeroitu järjestyksessä $1, 2, \dots, n$.

Olkoon tarvikkeiden nykyinen määrä kokonaisluku $x$, ja aluksi $x = 0$. $i$:ttä operaatiota kuvaa kaksi positiivista kokonaislukua $a_i, b_i$, ja tätä operaatiota suoritettaessa tapahtuvat vuorotellen seuraavat muutokset:

1. Ensin lukua $x$ kasvatetaan määrällä $a_i$ (eli asetetaan $x \leftarrow x + a_i$);
2. Sen jälkeen tarkistetaan luvun $x$ suuruus: jos tällöin $x > b_i$, lukua $x$ pienennetään arvoon $b_i$ (eli asetetaan $x \leftarrow \min(x, b_i)$).

Ennen operaatioiden suorittamisen aloittamista Pikku D voi tehdä listan järjestykseen enintään yhden muutoksen: valita minkä tahansa yhden operaation, poistaa sen paikaltaan ja siirtää sen jonon loppuun, jolloin muiden operaatioiden keskinäinen järjestys säilyy ennallaan (hän voi myös päättää olla tekemättä mitään muutosta).

Muutoksen jälkeen Pikku D suorittaa kaikki $n$ operaatiota uudessa järjestyksessä alusta loppuun peräkkäin, jokaisen operaation täsmälleen kerran. Pikku D haluaa tietää, kuinka suuri tarvikkeiden määrä $x$ voi enintään olla, kun kaikki operaatiot on suoritettu?

Syöte

Lue tiedot vuosta stdin.

Ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$, joka ilmaisee operaatioiden lukumäärän.

Seuraavista $n$ rivistä $i$:s rivi sisältää kaksi positiivista kokonaislukua $a_i, b_i$, jotka kuvaavat $i$:nnen operaation parametrit.

Tuloste

Kirjoita vuohon stdout.

Tulosta yksi rivi, joka sisältää yhden kokonaisluvun: tarvikkeiden määrän $x$ suurimman mahdollisen arvon kaikkien operaatioiden suorittamisen jälkeen.

Esimerkit

Syöte 1

3
1 100
100 90
1 1

Tuloste 1

90

Huomautus

Kun $2$. operaatio siirretään jonon loppuun, operaatioiden suoritusjärjestykseksi tulee $1, 3, 2$. Kunkin operaation suorittamisen jälkeen muuttujan $x$ arvoksi tulee vuorotellen $1, 1, 90$.

Jos $1$. operaatio siirretään loppuun, lopuksi $x = 2$; jos järjestystä ei muuteta tai $3$. operaatio siirretään loppuun, lopuksi $x = 1$. Näin ollen muuttujan $x$ suurin mahdollinen arvo on $90$.

Esimerkki 2

Katso kilpailijan hakemistossa olevat tiedostot supply/supply2.in ja supply/supply2.ans.

Tämä esimerkki täyttää testitapausten $1 \sim 4$ rajoitusehdot.

Esimerkki 3

Katso kilpailijan hakemistossa olevat tiedostot supply/supply3.in ja supply/supply3.ans.

Tämä esimerkki täyttää testitapausten $5 \sim 6$ rajoitusehdot.

Esimerkki 4

Katso kilpailijan hakemistossa olevat tiedostot supply/supply4.in ja supply/supply4.ans.

Tämä esimerkki täyttää testitapausten $7 \sim 10$ rajoitusehdot.

Rajoitukset

Kaikille syötteille pätee $1 \le n \le 2 \times 10^5$ ja $1 \le a_i, b_i \le 10^9$. Huomaa: syötteissä ei taata, että $a_i \le b_i$.

Tässä tehtävässä on yhteensä $10$ testitapausta, joista jokainen on $10$ pisteen arvoinen, ja jokainen testitapaus arvostellaan erikseen. Tarkat rajoitukset on esitetty alla olevassa taulukossa.

Erityisominaisuus A: $b_1 = b_2 = \dots = b_n$.