سرمایه‌گذاری کم‌دردسر


  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

فردا تولد حیدریه!

به همین دلیل حیدری احساس می‌کند پیر شده و به فکر بازنشستگی افتاده است.

اگر حیدری MM تومان پول در حسابش داشته باشد می‌تواند با خیال راحت بازنشسته شود. ولی متاسفانه در حال حاضر حساب حیدری خالیست!

خوش‌بختانه دوست حیدری، سلطانی، یک مولتی میلیاردر است که هر چقدر حیدری پول بخواهد به او برای سرمایه‌گذاری در بورس می‌دهد. (البته داوود هم یک مولتی میلیاردر است ولی از آن‌جایی که داوود خیلی خودش را می‌گیرد حیدری هرگز از او پولی درخواست نمی‌کند.)

در بازار بورس nn فرصت سرمایه‌گذاری وجود دارد که ii-امی آن‌ها ابتدا به cic_i تومان پول برای شروع نیاز دارد پس از سرمایه‌گذاری هر روز pip_i تومان سود می‌دهد. حیدری در هریک از این فرصت‌ها می‌تواند حداکثر یک بار سرمایه‌گذاری کند، اما او می‌تواند در هر چند فرصت مختلفی که بخواهد سرمایه‌گذاری کند. (حیدری کامپیوتری است؛ برای همین تواسته سود روزانه این فرصت‌ها را محاسبه کند.)

به حیدری کمک کنید تا روشی برای سرمایه‌گذاری انتخاب کند که در کوتاه ترین زمان بتواند تمام پول سلطانی را به او پس بدهد و برای خودش هم حداقل MM تومان پول بماند تا بتواند با خیال راحت بازنشسته شود.

به او بگویید این کوتاه‌ترین زمان چند روز است.

ورودی🔗

در خط اول وروردی دو عدد طبیعی nn و MM با فاصله از هم آمده است. 1n100 0001 \le n \le 100\ 000 1M1091 \le M \le 10^9 در nn خط بعدی در هر خط دو عدد آمده که به ترتیب pip_i و cic_i را نشان می‌دهد 1pi,ci1091 \le p_i, c_i \le 10^9

خروجی🔗

در تنها خط خروجی کم‌ترین تعداد روزی که لازم است تا حیدری بعد از پس دادن پول سلطانی MMتومان سود کند را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

2 5
4 10
10 15
Plain text

خروجی نمونه ۱🔗

2
Plain text

ورودی نمونه ۲🔗

4 10
1 8
3 12
4 17
10 100
Plain text

خروجی نمونه ۲🔗

6
Plain text

ورودی نمونه ۳🔗

3 5
4 1
9 10
6 3
Plain text

خروجی نمونه ۳🔗

1
Plain text