- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
فردا تولد حیدریه!
به همین دلیل حیدری احساس میکند پیر شده و به فکر بازنشستگی افتاده است.
اگر حیدری \(M\) تومان پول در حسابش داشته باشد میتواند با خیال راحت بازنشسته شود. ولی متاسفانه در حال حاضر حساب حیدری خالیست!
خوشبختانه دوست حیدری، سلطانی، یک مولتی میلیاردر است که هر چقدر حیدری پول بخواهد به او برای سرمایهگذاری در بورس میدهد. (البته داوود هم یک مولتی میلیاردر است ولی از آنجایی که داوود خیلی خودش را میگیرد حیدری هرگز از او پولی درخواست نمیکند.)
در بازار بورس \(n\) فرصت سرمایهگذاری وجود دارد که \(i\)-امی آنها ابتدا به \(c_i\) تومان پول برای شروع نیاز دارد پس از سرمایهگذاری هر روز \(p_i\) تومان سود میدهد. حیدری در هریک از این فرصتها میتواند حداکثر یک بار سرمایهگذاری کند، اما او میتواند در هر چند فرصت مختلفی که بخواهد سرمایهگذاری کند. (حیدری کامپیوتری است؛ برای همین تواسته سود روزانه این فرصتها را محاسبه کند.)
به حیدری کمک کنید تا روشی برای سرمایهگذاری انتخاب کند که در کوتاه ترین زمان بتواند تمام پول سلطانی را به او پس بدهد و برای خودش هم حداقل \(M\) تومان پول بماند تا بتواند با خیال راحت بازنشسته شود.
به او بگویید این کوتاهترین زمان چند روز است.
ورودی
در خط اول وروردی دو عدد طبیعی \(n\) و \(M\) با فاصله از هم آمده است. \[1 \le n \le 100\ 000\] \[1 \le M \le 10^9\] در \(n\) خط بعدی در هر خط دو عدد آمده که به ترتیب \(p_i\) و \(c_i\) را نشان میدهد \[1 \le p_i, c_i \le 10^9\]
خروجی
در تنها خط خروجی کمترین تعداد روزی که لازم است تا حیدری بعد از پس دادن پول سلطانی \(M\)تومان سود کند را چاپ کنید.
مثال
ورودی نمونه ۱
2 5
4 10
10 15
خروجی نمونه ۱
2
ورودی نمونه ۲
4 10
1 8
3 12
4 17
10 100
خروجی نمونه ۲
6
ورودی نمونه ۳
3 5
4 1
9 10
6 3
خروجی نمونه ۳
1