Кішкентай D жер шарын шарлау саяхатына дайындалып жатыр. Жолға шығар алдында ол жоспар бойынша тізімдегі жабдықтарды дайындауға арналған $n$ операцияны орындап шығуы керек, бұл операциялар бастапқыда ретімен $1, 2, \dots, n$ деп нөмірленген.

Ағымдағы жабдықтар санын $x$ бүтін санымен белгілейік, бастапқыда $x = 0$. $i$-ші операция екі оң бүтін $a_i, b_i$ сандарымен сипатталады, осы операцияны орындаған кезде ретімен келесі өзгерістер орын алады:

1. Алдымен $x$ мәнін $a_i$-ге арттырады (яғни $x \leftarrow x + a_i$ деп меншіктейді);
2. Одан кейін $x$ шамасын тексереді: егер осы сәтте $x > b_i$ болса, онда $x$ мәнін $b_i$-ге дейін қысқартады (яғни $x \leftarrow \min(x, b_i)$ деп меншіктейді).

Операцияларды орындауды бастамас бұрын, Кішкентай D тізім ретіне көп дегенде бір рет өзгеріс енгізе алады: кез келген бір операцияны таңдап, оны тізімнен алып, тізбектің соңына ауыстырады, ал қалған операциялардың салыстырмалы реті өзгеріссіз қалады (ешқандай өзгеріс жасамауды да таңдай алады).

Өзгеріс аяқталғаннан кейін, Кішкентай D жаңа ретпен басынан соңына дейін барлық $n$ операцияны ретімен, әр операцияны дәл бір реттен орындайды. Кішкентай D барлық операциялар орындалып болғаннан кейін жабдықтар саны $x$ ең көп дегенде қанша болуы мүмкін екенін білгісі келеді.

Кіріс деректер

Деректерді stdin ағынынан оқыңыз.

Бірінші жолда операциялар санын білдіретін бір оң бүтін $n$ саны берілген.

Келесі $n$ жолдың $i$-ші жолында $i$-ші операцияның параметрлерін сипаттайтын екі оң бүтін $a_i, b_i$ сандары берілген.

Шығыс деректер

Нәтижені stdout ағынына шығарыңыз.

Барлық операциялар орындалып болғаннан кейінгі жабдықтар саны $x$-тің ең үлкен мүмкін мәнін білдіретін бір бүтін санды бір жолға шығарыңыз.

Мысалдар

Кіріс деректер 1

3
1 100
100 90
1 1

Шығыс деректер 1

90

Ескертпе

$2$-ші операцияны тізбектің соңына ауыстырсақ, операциялардың орындалу реті $1, 3, 2$ болады. Әр операция орындалып болғаннан кейін $x$ мәні ретімен $1, 1, 90$ болып өзгереді.

Егер $1$-ші операцияны соңына ауыстырсақ, соңында $x = 2$ болады; егер ретін өзгертпесек немесе $3$-ші операцияны соңына ауыстырсақ, соңында $x = 1$ болады. Сондықтан $x$-тің ең үлкен мүмкін мәні $90$-ға тең.

Мысал 2

Қатысушы директориясындағы supply/supply2.in және supply/supply2.ans файлдарын қараңыз.

Бұл мысал $1 \sim 4$ тесттерінің шектеу шарттарын қанағаттандырады.

Мысал 3

Қатысушы директориясындағы supply/supply3.in және supply/supply3.ans файлдарын қараңыз.

Бұл мысал $5 \sim 6$ тесттерінің шектеу шарттарын қанағаттандырады.

Мысал 4

Қатысушы директориясындағы supply/supply4.in және supply/supply4.ans файлдарын қараңыз.

Бұл мысал $7 \sim 10$ тесттерінің шектеу шарттарын қанағаттандырады.

Шектеулер

Барлық деректер үшін $1 \le n \le 2 \times 10^5$, $1 \le a_i, b_i \le 10^9$ екеніне кепілдік беріледі. Назар аударыңыз: деректерде $a_i \le b_i$ болуына кепілдік берілмейді.

Бұл есепте барлығы $10$ тест бар, әр тест $10$ ұпаймен бағаланады және әр тест жеке есептеледі. Толық деректер ауқымы төмендегі кестеде көрсетілген.

Арнайы қасиет A: $b_1 = b_2 = \dots = b_n$.