Problem C
Bölk

Nú er komið að því að bölka fyrir ræktina, en til þess þarftu að kaupa í matinn. Þegar matur er keyptur á bölktíð skipta bara tveir hlutir máli: verð og hitaeiningafjöldi. Þú vilt sem mest út úr matnum svo þú vilt kaupa mat með sem flestar hitaeiningar, en þú mátt þó ekki eyða umfram mánaðarlaunin þín.

Í búðinni sem þú ert að versla eru $n$ vörur. Hver vara hefur verð $v$ í krónum og hitaeiningafjölda $h$. Fyrir hverja vöru getur þú annað hvort keypt hana eða ekki. Þú getur ekki keypt mörg eintök af sömu vörunni. Þú getur líka bara eytt samtals $c$ krónum.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $n$ og $c$ ($1 \leq n, c \leq 10^3$). Síðan koma $n$ línur sem hver inniheldur tvær heiltölur $v$ og $h$ ($0 \leq v, h \leq 10^6$). Hver þessara lína svarar til hlutar í búðinni sem kostar $v$ krónur og hefur $h$ hitaeiningar.

Úttak

Úttakið skal innihalda eina heiltölu, mesta fjölda hitaeininga sem unnt er að kaupa án þess að eyða meira en $c$ krónum samtals.

4 60
25 20
25 20
40 50
21 15

50