G. Moving Boxes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a large warehouse, there are $$$n$$$ boxes lined up in a straight row. Each box $$$i$$$ is initially placed at a location represented by the coordinate $$$x_i$$$. However, due to a reorganization plan, each box needs to be moved to a new position, $$$y_i$$$.

To assist with this reorganization, a specialized robot is at your disposal. This robot is designed to move at a speed of one unit of length per second and is capable of carrying only one box at any given time. The time taken by the robot to pick up and drop off boxes is negligible, but it requires $$$C$$$ seconds to change its direction. Initially, you can set the robot in any position and facing any direction. But after all boxes are relocated, the robot must return to its original position and direction. The boxes do not need to be transported to the destination all at once, which means they can be dropped off halfway. Additionally, multiple boxes can coexist in the same location during the process.

Your challenge is to strategize the robot's movements such that the total time to relocate all the boxes is minimized. Please calculate minimum total time required for the robot to relocate all boxes.

Input

The first line contains two integers $$$n$$$ and $$$C$$$ ($$$1\le n \le 10^5$$$, $$$1\le C\le 10^9$$$), indicating the number of boxes and the time cost for changing direction.

Each of the following $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1\le x_i,y_i\le 10^9$$$, $$$x_i \neq y_i$$$), indicating the initial position and the end position of box $$$i$$$. It is guaranteed that all $$$x_i$$$ are distinct from each other, and all $$$y_i$$$ are distinct from each other.

Output

Output a single integer denoting the minimum time for the robot to relocate all boxes.

Examples
Input
3 1
1 2
4 6
5 3
Output
12
Input
3 4
5 10
9 1
8 6
Output
38
Input
4 1
1 1001
1002 2
3 1003
1004 4
Output
4008
Note

Example 2: Start at position $$$1$$$, heading in the positive direction. Move to position $$$5$$$. Pick up box $$$1$$$. Move to position $$$8$$$. Drop off box $$$1$$$. Pick up box $$$3$$$. Change direction. Move to position $$$6$$$. Drop off box $$$3$$$. Change direction. Move to position $$$8$$$. Pick up box $$$1$$$. Move to position $$$10$$$. Drop off box $$$1$$$. Change direction. Move to position $$$9$$$. Pick up box $$$2$$$. Move to position $$$1$$$. Drop off box $$$2$$$. Change direction. The total time taken is $$$38$$$ seconds.

Example 3: Start at position $$$3$$$, heading in the positive direction. Pick up box $$$3$$$. Move to position $$$1003$$$. Drop off box $$$3$$$. Move to position $$$1004$$$. Pick up box $$$4$$$. Change direction. Move to position $$$1002$$$. Drop off box $$$4$$$. Pick up box $$$2$$$. Move to position $$$2$$$. Drop off box $$$2$$$. Move to position $$$1$$$. Pick up box $$$1$$$. Change direction. Move to position $$$1001$$$. Drop off box $$$1$$$. Move to position $$$1002$$$. Pick up box $$$4$$$. Change direction. Move to position $$$4$$$. Drop off box $$$4$$$. Move to position $$$3$$$. Change direction. The total time taken is $$$4008$$$ seconds.