Праздник сена
Праздник сена
Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется n стогов сена. i-ый стог имеет опредённый вкус fi
(1 ≤ fi
≤ 109
) и определённую пряность si
(1 ≤ si
≤ 109
).
Еда будет представлять собой непрерывный интервал, содержащий один или более последовательных стогов сена (нельзя менять их порядок). Общий вкус еды равен сумме вкусов на интервале. Общая пряность еды - максимум из пряностей на интервале.
ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее m.
Входные данные
Первая строка содержит целые числа n (1 ≤ n ≤ 105
) и m (1 ≤ m ≤ 1018
) - количество стогов сена и минимальный вкус, которого нужно достичь, соответственно. Следующие n строк описывают n стогов сена парой чисел в строке - первое вкус f, а второе - пряность s.
Выходные данные
Выведите минимальную пряность, которую можно достичь при выполнении требования о минимальном вкусе. Гарантируется существование решеня.
5 10 4 10 6 15 3 5 4 9 3 6
9