Zhenya the Glider Pilot#8704
A plane is flying parallel to the Earth's surface at a height of meters. The plane travels from point (-10^9, h) to point (10^9, h) along the axis, moving to the right.
Onboard the plane is a glider pilot named Zhenya, who will jump out at a specific moment. For this task, the glider can only jump from integer coordinates. After jumping, each second, he moves one unit to the right along the axis and descends one unit downward.
There are several segments with updrafts, each defined by two numbers x_1 and x_2 (x_1 < x_2), which extend vertically through the entire height. No two updrafts overlap or touch. When the glider enters an updraft, he maintains his altitude while within it, although he continues to move one unit to the right per second. Your task is to determine the maximum distance along the axis that the glider can travel from his jump point to his landing point, given that he can choose his jump point freely. Once the glider reaches the ground, he stops, meaning he cannot continue gliding in an updraft at height .
For example, if the glider jumps at coordinate , he will land at . If he jumps at coordinate , he will land at .
The first line contains two integers and (1 \leq n \leq 2 \cdot 10^5, 1 \leq h \leq 10^9) — the number of updrafts and the flight height of the plane.
Each of the next lines contains two integers x_{i1} and x_{i2} (1 \leq x_{i1} < x_{i2} \leq 10^9) — the coordinates of the left and right ends of the i-th updraft. It is guaranteed that no two updrafts intersect or share common points.
Print the maximum distance along the axis from the jump point to the landing point that the glider can achieve, given that he can choose his jump point freely. It is guaranteed that the answer is an integer under the given constraints.
Example 1
Example 2
Example 3
In the first example, it is optimal for the glider to jump at the point with coordinates , landing at . The distance is 12 - 2 = 10. In the second example, the best jump is at , landing at , resulting in a distance of 34 - 16 = 18. In the third example, the glider can jump at , landing at , with a distance of 1999999899 - (-100) = 1999999999.