Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется \(N\)
стогов сена (\(1 \le N \le 100,000\)). \(i\)-ый стог имеет опредённый вкус \(F_i\)
(\(1 \le F_i \le 10^9\)) и определённую пряность \(S_i\) (\(1 \le S_i \le 10^9\)).
Еда будет представлять собой непрерывный интервал, содержащий один или более
последовательных стогов сена (нельзя менять их порядок). Общий вкус еды равен
сумме вкусов на интервале. Общая пряность еды - максимум из пряностей на интервале.
ФД хочет определить минимальную пряность, кторую можно достичь, чтобы
вкус был не менее \(M\) (\(1 \le M \le 10^{18}\)).
ФОРМАТ ВВОДА (файл hayfeast.in):
Первая строка содержит целые числа \(N\) и \(M\), количество стогов сена и минимальный
вкус, которого нужно достичь, соответственно. Следующие \(N\) строк описывают \(N\)
стогов сена парой чисел в строке - первое вкус \(F\), а второе - пряность \(S\).
ФОРМАТ ВЫВОДА (файл hayfeast.out):
Выведите минимальную пряность, которую можно достичь при выполнении требования
о минимальном вкусе. Гарантируется существование решеня.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 10
4 10
6 15
3 5
4 9
3 6
|
9
|