Lille D förbereder en jordenruntresa. Före avresan måste han enligt plan genomföra $n$ operationer för förberedelse av förnödenheter på sin lista, vilka från början är numrerade i ordning som $1, 2, \dots, n$.

Låt den aktuella mängden förnödenheter vara ett heltal $x$, där $x = 0$ från början. Den $i$-te operationen beskrivs av två positiva heltal $a_i, b_i$, och när denna operation utförs sker följande förändringar i tur och ordning:

1. Först ökas $x$ med $a_i$ (det vill säga sätt $x \leftarrow x + a_i$);
2. Därefter kontrolleras storleken på $x$: om $x > b_i$ vid detta tillfälle minskas $x$ till $b_i$ (det vill säga sätt $x \leftarrow \min(x, b_i)$).

Innan utförandet av operationerna påbörjas får Lille D göra högst en justering av listans ordning: välja en godtycklig operation, ta ut den och flytta den till slutet av följden, medan den inbördes ordningen mellan de övriga operationerna förblir oförändrad (han kan också välja att inte göra någon justering alls).

När justeringen är klar kommer Lille D att utföra alla $n$ operationer i tur och ordning från början till slut enligt den nya ordningen, där varje operation utförs exakt en gång. Lille D vill veta: när alla operationer har utförts, vilket är det största möjliga värdet på mängden förnödenheter $x$?

Indata

Läs indata från stdin.

Den första raden innehåller ett positivt heltal $n$, som anger antalet operationer.

De följande $n$ raderna innehåller på den $i$-te raden två positiva heltal $a_i, b_i$, vilka beskriver parametrarna för den $i$-te operationen.

Utdata

Skriv till stdout.

Skriv ut en rad med ett heltal, som anger det största möjliga värdet på mängden förnödenheter $x$ efter att alla operationer har utförts.

Exempel

Indata 1

3
1 100
100 90
1 1

Utdata 1

90

Förklaring

Om den $2$:a operationen flyttas till slutet av följden blir utförandeordningen för operationerna $1, 3, 2$. Efter att varje operation har utförts blir värdet på $x$ i tur och ordning $1, 1, 90$.

Om den $1$:a operationen flyttas till slutet blir det slutliga värdet $x = 2$; om ordningen inte justeras eller om den $3$:e operationen flyttas till slutet blir det slutliga värdet $x = 1$. Därför är det största möjliga värdet på $x$ lika med $90$.

Exempel 2

Se supply/supply2.in och supply/supply2.ans i tävlingsdeltagarens katalog.

Detta exempel uppfyller villkoren för testfallen $1 \sim 4$.

Exempel 3

Se supply/supply3.in och supply/supply3.ans i tävlingsdeltagarens katalog.

Detta exempel uppfyller villkoren för testfallen $5 \sim 6$.

Exempel 4

Se supply/supply4.in och supply/supply4.ans i tävlingsdeltagarens katalog.

Detta exempel uppfyller villkoren för testfallen $7 \sim 10$.

Begränsningar

För alla data garanteras att $1 \le n \le 2 \times 10^5$ och $1 \le a_i, b_i \le 10^9$. Observera: data garanterar inte att $a_i \le b_i$.

Detta problem har totalt $10$ testfall, vart och ett värt $10$ poäng, och varje testfall bedöms oberoende. Detaljerade begränsningar visas i tabellen nedan.

Särskild egenskap A: $b_1 = b_2 = \dots = b_n$.