6. Strieborné bubáky

Bubu sa rozhodol, že si zaobstará nejaké tie strieborné bubáky. Lenže bubáky nerastú len tak na strome. Pre bežných smrteľníkov je dosť náročná úloha niekde také bubáky zohnať. Bubu však nie je žiadny amatér a vie, ako na to.

Existuje totiž stará baňa, v ktorej trpaslíci zakopali svoje poklady. A Bubuho plán je ich vykopať. Miesto už pozná, potrebuje si už len zaobstarať správne vybavenie, konkrétne dobrý krompáč. Čím lepší krompáč, tým viac ním Bubu vyťaží. Lenže lepšie krompáče zvyčajne aj viac stoja.

Bolo by treba vymyslieť optimálnu stratégiu nakupovania krompáčov. Bubu by si to v skutočnosti vedel spočítať aj sám, ale zrovna sa mu nechce. A tak prichádzate do hry vy.

Úloha

Na začiatku (v deň 0) má Bubu našetrených \(B\) strieborných bubákov.

Na trhu sa dá zohnať \(N\) krompáčov. Krompáč \(i\) (\(1 \leq i \leq N\)) bude dostupný iba v deň \(i\), stojí \(c_i\) bubákov a Bubu ním vykope \(b_i\) bubákov za deň. Bubu si môže kúpiť nový krompáč iba v prípade, že má dosť peňazí, t.j. ak má aspoň \(c_i\) bubákov. Keď tak spraví, starý krompáč okamžite zahodí a potom používa nový krompáč, až kým ho znovu nevymení za ďalší.

Koľko najviac bubákov vie mať Bubu v deň \(N+1\), ak zvolí správne dni, kedy nakúpiť krompáče?

Formát vstupu

V prvom riadku je \(N\) a \(B\) - počet krompáčov a začiatočný počet bubákov. Nasleduje \(N\) riadkov, v \(i\)-tom z nich sú dve čísla \(c_i, b_i\) - cena \(i\)-teho krompáča a počet bubákov, ktoré ním Bubu vykope za deň.

Formát výstupu

Vypíšte jedno číslo - najväčší počet bubákov, ktorý vie mať Bubu v deň \(N+1\).

Hodnotenie

V prvej sade platí \(1 \leq N \leq 1\,000\), \(1 \leq c_i, b_i \leq 1\,000\).

V druhej sade platí \(1 \leq N \leq 200\,000\), \(1 \leq c_i, b_i \leq 10^9\).

Príklady

Input:

5 10
1 1
11 100
11 10
1 5
20 15

Output:

30

V prvom dni si Bubu kúpi krompáč. V druhom dni si nemôže dovoliť krompáč za \(11\), ale v treťom dni už áno a kúpi si ho. Tým za ďalšie tri dni vyťaží \(30\) bubákov. Ak by si kúpil krompáč aj v posledný deň, vedel by ním síce ťažiť viac, ale stojí \(20\) bubákov, a tak by skončil v deň \(N+1\) len s \(15\) bubákmi.