Кристали#10969

Кристали

1 секунда

256 мегабайтів

Легка

У вас є чарівна машина, яка генерує золото, використовуючи кристали.

У вас є $n$ кристалів. Щоб запустити генератор, вам потрібно вставити в нього один кристал. За один запуск $i$ -го кристалу у звичайному режимі, машина згенерує $a_{i}$ a_i кілограм золота. Після такого запуску цей кристал можна використовувати знову. Також можна запустити генератор у посиленому режимі, у якому він згенерує не $a_{i}$ a_i кілограм, а $b_{i}$ b_i. Проте після такого запуску кристал зламається.

Вам потрібно згенерувати хоча б $k$ кілограм золота. За яку мінімальну кількість запусків це можна зробити?

Вхідні дані

Перший рядок містить два цілі числа $n$ та $k$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5, $1 \leq k \leq 1 0^{9}$ 1 \leq k \leq 10^9).

Кожен з наступних $n$ рядків містить по два цілі числа $a_{i}$ a_i та $b_{i}$ b_i ( $1 \leq a_{i} \leq b_{i} \leq 1 0^{9}$ 1 \leq a_i \leq b_i \leq 10^9).

Вихідні дані

Виведіть одне ціле число.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі можна, наприклад, використати у звичайному режимі другий кристал, отримавши $8$ кілограмів. Потім використати перший кристал у звичайному режимі, отримавши $7$ кілограмів. Потім використати другий кристал у посиленому режимі, отримавши $9$ кілограмів. Можна помітити, що за два запуски отримати $20$ кілограмів неможливо.

Оцінювання

Рішення, які правильно працюють для $n, k, a_{i}, b_{i} \leq 100$ n, k, a_i, b_i \leq 100, отримають принаймні $35$ балів.

Рішення, які правильно працюють для $n, k, a_{i}, b_{i} \leq 2000$ n, k, a_i, b_i \leq 2\,000, отримають принаймні $70$ балів.