eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Финансовое планирование

Финансовое планирование

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Будучи ответственным молодым человеком, Вы решили начать планировать выход на пенсию. Проведя некоторые предварительные расчеты, Вы пришли к выводу, что вам нужно как минимум m евро, чтобы комфортно выйти на пенсию.

В настоящее время Вы разорены, но, к счастью, щедрый друг-миллионер предложил Вам одолжить произвольную сумму денег (столько, сколько Вам нужно), без процентов, для инвестирования в фондовый рынок. Получив некоторую прибыль, Вы вернете первоначальную сумму своему другу, оставив себе остаток.

Вам доступны n инвестиционных возможностей, i-я из которых стоит c_i евро. Вы также использовали свои навыки информатики, чтобы спрогнозировать, что i-я инвестиция принесет вам p_i евро в день. Какое наименьшее количество дней Вам необходимо, чтобы расплатиться с другом и выйти на пенсию? Вы можете инвестировать только один раз в каждую инвестиционную возможность. Однако Вы можете инвестировать в столько различных инвестиционных возможностей, во сколько захотите.

Рассмотрим первый пример. Если Вы купите только вторую инвестицию (которая стоит 15 евро), то заработаете p_2 = 10 евро в день. Через два дня заработать 20 евро — ровно столько чтобы расплатиться с другом (у которого вы заняли 15 евро) и уйти на пенсию с оставшейся прибылью (5 евро). Невозможно заработать чистую сумму в 5 евро за один день, поэтому два дня — это самый быстрый вариант.

Вхідні дані

В первой строке задано количество вариантов инвестирования n~(1 \le n \le 10^5) и минимальная сумма денег m~(1 \le m \le 10^9), которая Вам необходима для выхода на пенсию.

Затем следуют n строк. В i-ой строке есть два целых числа: ежедневная прибыль от этой инвестиции p_i~(1 \le p_i \le 10^9) и ее первоначальная стоимость c_i~(1 \le c_i \le 10^9).

Вихідні дані

Выведите наименьшее количество дней, необходимое для того, чтобы окупить Ваши инвестиции и выйти на пенсию, по крайней мере, с m евро, если Вы следуете оптимальной инвестиционной стратегии.

Приклад

Вхідні дані #1
2 5
4 10
10 15
Вихідні дані #1
2
Вхідні дані #2
4 10
1 8
3 12
4 17
10 100
Вихідні дані #2
6
Вхідні дані #3
3 5
4 1
9 10
6 3
Вихідні дані #3
1
Джерело 2018 Benelux Algorithm Programming Contest (BAPC), Problem F