eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

Літак летить паралельно поверхні землі на висоті h метрів. Будемо вважати, що літак летить з точки(−10^9, h) в точку (10^9,h)паралельно осі Ox праворуч.

ris4.jpg

У літаку знаходиться планерист Женя, який в певний момент вистрибне з літака. Через особливості завдання, планерист може вистрибувати тільки в цілочисельних координатах. Після стрибка кожну секунду він буде рухатися вздовж осі Ox на одиницю вправо, а також падати на одиницю вниз.На деяких відрізках діють висхідні потоки повітря, які характеризуються двома числами x[1] і x[2] (x1 < x2). Вони діють по всій висоті. Ніякі два потоки не перетинаються і не мають спільних точок. Якщо планерист потрапляє в висхідний потік, то він не втрачає висоту, поки летить в цьому потоці. Зміна по осі Ox залишається такою ж - він рухається на одиницю вправо за одну секунду.Визначте максимальну відстань по осі Ox від точки стрибка до точки приземлення, яку планерист зможе пролетіти, якщо він самостійно може вибрати точку стрибка. Торкнувшись землі, планерист зупиняється, тобто він не може планувати в висхідному потоці на висоті 0.Якщо планерист вистрибне в координаті 1, То він зупиниться в 10. Якщо ж він вистрибне в точці 2, то зупиниться в точці 12.####Вхідні дані

Перший рядок містить два цілих числа n і h (1≤n≤2⋅10^5,1≤h≤10^9) - кількість висхідних потоків повітря і висота польоту літака.

Кожен з наступних n рядків містить два цілих числа xi1 і xi2 (1 ≤ xi1 < xi2 ≤ 10^9) - координати лівого і правого кінців i-го висхідного потоку. Гарантується, що ніякі два потоки не перетинаються і не мають спільних точок

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

####Примітка

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

Examples

Input example #1
3 4
2 5
10 11
7 9
Output example #1
10
Input example #2
5 10
5 7
11 12
16 20
25 26
30 33
Output example #2
18
Input example #3
1 1000000000
1 1000000000
Output example #3
1999999999
Source ІІІ етап Всеукраїнської олімпіади з інформатики 2019