Женя планерист#8704

Женя планерист

1 секунда

64 мегабайти

Середня

Літак летить паралельно поверхні землі на висоті $h$ метрів. Літак рухається з точки $(- 1 0^{9}, h)$ (-10^9, h) у точку $(1 0^{9}, h)$ (10^9, h) уздовж осі $O x$ праворуч.

У літаку знаходиться планерист Женя, який у певний момент вистрибне з літака. За умовами задачі, планерист може стрибнути тільки у точках із цілими координатами. Після стрибка кожної секунди він буде рухатися вздовж осі $O x$ на одну одиницю вправо, а також падати на одну одиницю вниз.

На деяких відрізках діють висхідні потоки повітря, які задаються двома числами $x_{1}$ x_1 та $x_{2}$ x_2 ( $x_{1} < x_{2}$ x_1 < x_2). Вони діють по всій висоті. Жодні два потоки не перетинаються і не мають спільних точок. Якщо планерист потрапляє у висхідний потік, то він не втрачає висоти, поки знаходиться у ньому, але рух уздовж осі $O x$ залишається таким же — він рухається на одну одиницю вправо за одну секунду. Визначте максимальну відстань по осі $O x$ від точки стрибка до точки приземлення, яку планерист може пролетіти, якщо він самостійно вибирає точку стрибка. Торкнувшись землі, планерист зупиняється, тобто він не може планувати у висхідному потоці на висоті $0$ .

Якщо планерист вистрибне у координаті $1$ , то він зупиниться у $10$ . Якщо ж він вистрибне у точці $2$ , то зупиниться у точці $12$ .

Вхідні дані

Перший рядок містить два цілих числа $n$ і $h$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^5, $1 \leq h \leq 1 0^{9}$ 1 \leq h \leq 10^9) — кількість висхідних потоків повітря і висота польоту літака.

Кожен з наступних $n$ рядків містить два цілих числа $x_{i 1}$ x_{i1} і $x_{i 2}$ x_{i2} ( $1 \leq x_{i 1} < x_{i 2} \leq 1 0^{9}$ 1 \leq x_{i1} < x_{i2} \leq 10^9) — координати лівого і правого кінців $i$ -го висхідного потоку. Гарантується, що жодні два потоки не перетинаються і не мають спільних точок.

Вихідні дані

Виведіть максимальну відстань по осі $O x$ від точки стрибка до точки приземлення, яку планерист зможе пролетіти, якщо він самостійно може вибрати точку стрибка. Гарантується, що при заданих обмеженнях відповідь — ціле число.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі планеристу вигідно вистрибнути у точці з координатами $(2, 4)$ , тоді він приземлиться у точці $(12, 0)$ . У цьому випадку відстань дорівнює $12 - 2 = 10$ 12 - 2 = 10.У другому прикладі планеристу вигідно вистрибнути у точці з координатами $(16, 10)$ , тоді він приземлиться у точці $(34, 0)$ . У цьому випадку відстань дорівнює $34 - 16 = 18$ 34 - 16 = 18.У третьому прикладі планерист може вистрибнути, наприклад, у точці $(- 100, 1000000000)$ , тоді він приземлиться у $(1999999899, 0)$ . У цьому випадку відстань дорівнює $1999999899 - (- 100) = 1999999999$ 1999999899 - (-100) = 1999999999.