+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! به همین دلیل حیدری احساس می‌کند پیر شده و به فکر بازنشستگی افتاده است. اگر حیدری $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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> تلاش کنید با باینری سرچ روی جواب (کمینه تعداد روز) جواب را بیابید. هنگام زدن باینری سرچ، یک مقدار $d$ داریم و باید چک کنیم که آیا می‌توان به میزان $M$ سود در $d$ روز رسید یا خیر. در راهنمایی بعدی، روشی برای یافتن این که آیا در $d$ روز می‌توان به هدف رسید را توضیح می‌دهیم. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> فرض کنید می‌خواهیم کار را در $d$ روز تمام کنیم. در این صورت وضوح بهتر است تمام فرصت‌هایی را که سودی که در $d$ روز می‌دهند بیش‌تر از سرمایه اولیه مورد نیاز آن‌هاست،‌ انتخاب کنیم. پس از انتخاب تمام فرصت ها با این ویژگی می‌توانیم چک کنیم که آیا پس از این $d$ روز توانسته‌ایم $M$ تومان سود کنیم یا خیر. </details>

حل سؤال در بانک سؤالات