Problem A
Bruni Íslenskra Fræða

Nú er Atli endanlega genginn af göflunum. Eftir að hafa verið fenginn til að lesa enn eina íslendingasöguna brast eitthvað í toppstykkinu hjá honum og gengur hann nú berserksgang um Hús Íslenskra Fræða. Hann hefur ákveðið að reyna kveikja bál í sem flestum ritverkum hússins. Hann er búinn að kveikja eld sem mun lifa í $t$ sekúndur. Til þess að lengja líftíma bálsins hleypur hann um og safnar ritverkum og bókum til að henda á bálið. Verandi vel vanur forritari er Atli auðvitað búinn að finna út úr bestu leiðinni til að framkvæma plan sitt þrátt fyrir að vera orðinn snarbilaður. Verk þitt er nú að finna út úr því hvað eldurinn mun brenna lengi svo háskólinn viti hvað þeir hafa langan tíma til að stoppa hann.

Inntak

Inntakið byrjar á einni línu með tveimur heiltölum $1 \leq n, t \leq 10^3$ þar sem $n$ er fjöldi ritverkasafna Atli getur sótt og $t$ er líftími eldsins í sekúndum. Næst koma $n$ línur, hver með tveimur heiltölum $1 \leq t_ i, f_ i \leq 10^3$. Þetta gefur eitt ritverkasafn sem Atli getur sótt. Það tekur Atla $t_ i$ sekúndur að sækja staflann og hann lengir líftíma eldsins um $f_ i$ sekúndur. Til að nýta staflann þarf eldurinn enn að vera í gangi þegar hann er búinn að sækja staflann. Ef eldurinn deyr á sömu sekúndu og hann kemur til baka getur hann notað heitu öskuna til að kveikja í staflanum.

Úttak

Prentið hvað Atli getur haldið eldinum gangandi lengi í sekúndum.

3 10
10 20
15 5
12 6

36