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