Problem F
Framkvæmdir

Það er orðið tímabært að byggja ný salerni fyrir barinn þinn. Salerni eru dýr svo þú vilt byggja eins fá salerni og þú getur, en vilt samt tryggja að enginn gestur þurfi að bíða í röð til að komast á salernið. Með notkun einnota plastglasa hefur þú safnað saman lífkennum allra $n$ gesta síðustu vikna.

Gestur drekkur í $b$ sekúndur þar til blaðra gestsins fyllist. Gesturinn fer svo á laust salerni og er þar í $d$ sekúndur og byrjar svo aftur að drekka um leið og salernisferð lýkur. Þetta heldur áfram í $t$ sekúndur, þá lokar barinn. Á þessum tímapunkti má enginn fara á salernið.

Allir gestir byrja að drekka á sama tíma. Öll salerni rúma einn gest í einu og þökk sé afkynjun salerna, sem mun örugglega hækka ESG-stig barsins, getur sérhver gestur notað sérhvert salerni. Gestir labba framhjá hvorum öðrum á leiðinni inn og út úr salernunum samstundis án óþæginda.

Input

• Ein lína með fjölda gesta $n\in \{ 1,\ldots , 10000\} $ og lokunartíma $t\in \{ 1,\ldots , 500\, 000\} $.

• Svo $n$ línur, þar sem $i$-ta þeirra gefur blöðrustærð $b_i\in \{ 1000,\ldots , 7200\} $ og fráskilstíma $d_i\in \{ 100, \ldots , 1800\} $ hjá $i$-ta gesti.

Output

Lágmarksfjölda salerna sem þarf.

2 4000
1000 500
1500 1000

1

2 4001
1000 500
1500 1000

2

1 1000
1000 100

0