Sticks

There is a game played with sticks of various lengths. Before the game starts, you draw two parallel horizontal lines a distance $L$ apart on a desk, and you place each stick so that its two ends lie one on the upper line and one on the lower line. Several stick ends may meet at a single point on a line, but no two sticks completely overlap.

Each stick is written as $(t, d)$, where $t$ is its coordinate on the upper line and $d$ is its coordinate on the lower line. In Figure 1 below, stick $a$ is $(1, 0)$ and stick $b$ is $(6, 0)$.

The goal of the game is to remove some of the placed sticks so that the remaining sticks form a single zigzag line satisfying all three conditions below.

1. The sticks touch only at endpoints and otherwise do not cross one another.
2. No point has three or more stick ends meeting at it.
3. All sticks are connected to one another.

The winner is whoever makes the longest zigzag line. The length of a zigzag line is the sum of the lengths of its sticks, and the length of one stick is its horizontal distance plus its vertical distance between the two endpoints. For a stick $(t, d)$ the horizontal distance is $|t - d|$ and the vertical distance is $L$, the gap between the two lines. In the figure above, the stick lengths are as follows.

For example, in Figure 1 keeping only sticks $a, b, e$ gives a zigzag line that satisfies all three conditions, with length $4 + 9 + 4 = 17$. Keeping only sticks $c, e$ also satisfies all three conditions, with length $6 + 4 = 10$. Keeping only sticks $b, c$ violates condition 1, keeping only $c, d, e$ violates condition 2, and keeping only $a, b, g$ violates condition 3. The longest zigzag line is made of sticks $c, d, f, g$ with length $6 + 4 + 7 + 3 = 20$.

Given the initial arrangement of the sticks, write a program that finds the length of the longest zigzag line that can be formed.

The first line contains two integers $N$ and $L$ separated by a space: the number of sticks and the gap between the two horizontal lines. Here $1 \le N \le 100{,}000$ and $1 \le L \le 1{,}000{,}000$.

Each of the next $N$ lines contains two integers $t$ and $d$ separated by a space, describing one stick $(t, d)$. Here $0 \le t, d \le 100{,}000{,}000$. No two sticks in the input completely overlap.

Print the length of the longest zigzag line on a single line.

Intermediate values and the answer can exceed the range of a 32-bit integer, so using a 64-bit integer type is recommended.