Фінансове планування#9883
Будучи відповідальною молодою людиною, ви вирішили заздалегідь подбати про пенсію. Прикинувши нашвидкуруч, ви з'ясували, що для безбідного життя на пенсії вам знадобиться не менше євро.
Зараз у вас немає жодної копійки, але, на щастя, ваш щедрий друг-мультимільярдер запропонував позичити вам без відсотків скільки завгодно грошей для вкладення у фондовий ринок. Отримавши прибуток, ви повернете другові позичену суму, а решту залишите собі.
Вам доступно інвестиційних можливостей, -та з яких коштує c_i євро. За допомогою своїх навичок в інформатиці ви також передбачили, що -та інвестиція приноситиме вам p_i євро на день. У кожну можливість можна вкластися не більше одного разу, але вкладатися можна у скільки завгодно різних можливостей. За яку мінімальну кількість днів ви зможете розрахуватися з другом і вийти на пенсію?
Розглянемо, наприклад, перший тест. Якщо купити тільки другу інвестицію (вартістю євро), вона приноситиме p_2 = 10 євро на день. Через два дні ви заробите євро — рівно стільки, щоб повернути другові позичені євро і вийти на пенсію з рештою євро прибутку. Заробити чистий прибуток у євро за один день неможливо, тому два дні — найкраща можлива відповідь.
У першому рядку задано кількість інвестиційних можливостей n~(1 \le n \le 10^5) та мінімальну суму грошей m~(1 \le m \le 10^9), необхідну для виходу на пенсію.
Кожен з наступних рядків містить два цілих числа: щоденний прибуток p_i~(1 \le p_i \le 10^9) від -ї інвестиції та її початкову вартість c_i~(1 \le c_i \le 10^9).
Виведіть мінімальну кількість днів, необхідну, щоб розрахуватися з другом і вийти на пенсію, маючи не менше євро, за оптимальної стратегії інвестування.
Приклад 1
Приклад 2
Приклад 3