E. Cookie Clicker
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Костя играет в компьютерную игру Cookie Clicker, основная цель которой — накопление запасов печенья. Получать печенья можно с помощью различных строений: можно просто кликать по специальному полю на экране, получая печенья за клики, можно купить фабрику печеньев, алхимическую лабораторию, машину времени, и все это будет приносить много-много печеньев.

В начале игры (момент времени 0) у Кости есть 0 печеньев и ни одного строения. На его выбор доступно n строений: i-ое строение стоит ci печеньев и в конце каждой секунды приносит vi печеньев. Кроме того, чтобы играть было еще интереснее, Костя решил поставить себе ограничение: в каждый момент времени он будет использовать только одно строение. Разумеется, он может по своему усмотрению менять активное строение каждую секунду.

Важно, что в версии игры, в которую играет Костя, покупать новые строения и менять активное строение можно только в моменты времени, кратные одной секунде. В один момент времени Костя может купить новое строение и тут же начать его использовать. Если Костя начал использовать строение в момент времени t, то первую прибыль оно сможет принести лишь в момент времени t + 1.

Костя хочет заработать не менее s печеньев как можно быстрее. Определите, за сколько секунд он сможет это сделать.

Входные данные

В первой строке находятся два целых числа n и s (1 ≤ n ≤ 2·105, 1 ≤ s ≤ 1016) — количество строений в игре и количество печеньев, которое Костя хочет заработать.

В каждой из следующих n строк записано два целых числа vi и ci (1 ≤ vi ≤ 108, 0 ≤ ci ≤ 108) — количество печеньев, которое приносит i-ое строение за одну секунду, и стоимость этого строения.

Выходные данные

Выведите единственное целое число — минимальное количество секунд, за которое Костя сможет заработать не менее s печеньев. Гарантируется, что он может это сделать.

Примеры
Входные данные
3 9
1 0
2 3
5 4
Выходные данные
6
Входные данные
3 6
1 0
2 2
5 4
Выходные данные
5
Входные данные
3 13
1 0
2 2
6 5
Выходные данные
7
Входные данные
1 10000000000000000
1 0
Выходные данные
10000000000000000