Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется n стогов сена. i-ый стог имеет опредённый вкус fi (1 ≤ fi ≤ 109) и определённую пряность si (1 ≤ si ≤ 109).

Еда будет представлять собой непрерывный интервал, содержащий один или более последовательных стогов сена (нельзя менять их порядок). Общий вкус еды равен сумме вкусов на интервале. Общая пряность еды - максимум из пряностей на интервале.

ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее m.

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

Первая строка содержит целые числа n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 1018) - количество стогов сена и минимальный вкус, которого нужно достичь, соответственно. Следующие n строк описывают n стогов сена парой чисел в строке - первое вкус f, а второе - пряность s.

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

Выведите минимальную пряность, которую можно достичь при выполнении требования о минимальном вкусе. Гарантируется существование решеня.