- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سال ۱۴۹۹ است و دیجی‌کال‍ا از رمزارز خود با نام دیجی‌رمز رونمایی کرده است!
علی می‌خواهد از طریق سرمایه‌گذاری در این رمزارز، $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
اگر علی ۲ روز در فرصت سرمایه‌گذاری دوم سرمایه‌گذاری کند، به اندازه‌ی $$2 \times 10 - 15 = 5 \geq 5$$ سود می‌کند و به هدفش می‌رسد.
ورودی نمونه ۲
4 10
1 8
3 12
4 17
10 100
خروجی نمونه ۲
6
اگر علی ۶ روز در فرصت سرمایه‌گذاری دوم و سوم سرمایه‌گذاری کند، به اندازه‌ی $$(6 \times 3 - 12) + (6 \times 4 - 17) = 6 + 7 = 13 \geq 10$$ سود می‌کند و به هدفش می‌رسد.
ورودی نمونه ۳
3 5
4 1
9 10
6 3
خروجی نمونه ۳
1
اگر علی ۱ روز در فرصت سرمایه‌گذاری اول و سوم سرمایه‌گذاری‌کند، به اندازه‌ی $$(1 \times 4 - 1) + (1 \times 6 - 3) = 3 + 3 = 6 \geq 5$$ سود می‌کند و به هدفش می‌رسد.
ارسال پاسخ برای این سؤال