Description
An ant is responsible for tidying up the nest. Every day, it patrols a straight path of length M, starting at position 0 and moving to position M. Along the way, there are N pieces of food scattered on the path. The i-th piece of food Fi is at position Si and needs to be moved to position Ei. The ant can only carry one piece of food at a time. What is the shortest total distance the ant needs to travel to move all the food to their correct positions and end at position M?
For example,
N = 2, M = 10
S1 = 0, E1 = 9
S2 = 6, E2 = 5
The ant always starts at location 0. It first picks up food F1 at location 0 and carries F1 to position 6 and puts down F1. Then, it picks up F2, and then carries F2 to position 5. Next, it can go to position 6 to pick up F1 and carry it to position 9. Note that the ant must arrive at position 10 at last. Thus, the minimum total distance is 6+1+1+3+1=12.
Input
Each test case begins with a line containing two integers N and M, which are the number of food and the path length in the nest, respectively.
The next N lines, each contains 2 integers Si, Ei which denote the start position and end position of food Fi, respectively.
Please note:
1 ≤ N ≤ 500,000
0 ≤ Si, Ei ≤ M ≤ 109.
Output
Print the minimum total distance required. A newline is added after the minimum total distance