레이팅 미적용In the far away land there is a big river and a number of villages beside it. Villages are numbered 0
through M, in order along the river. Distance bewteen consecutive villages is exactly 1 mile.
Mirko lives in the village marked with 0. He is in the business of transporting people between villages
with his boat. Today, Mirko will travel from his village to village M, and he will also transport some
people along the way.
There are N people that wish to travel today, and for each of them we know their starting point as well
as their destination. Mirko's boat can accommodate as many people as needed.
Let's say for example that person A is traveling from village 2 to village 8, and B from village 6 to
village 4. Mirko will, as always, start from his village 0, pick up A at village 2, pickup B at 6, go back to 4
and leave B there, proceed to village 8, leave A there, and then continue to his final destination, village
M. This scenario is given in the first test case below.
Write a program that will find the minimum number of miles that Mirko must travel in order to
transport everyone to their destinations and reach village M at the end.
In test cases worth a total of 40% points, \(N \le 5000\) will hold.
In test cases worth a total of 50% points, \(M \le 2000000\) will hold.
EXAMPLE TEST DATA
input
2 10
2 8
6 4
output
14
input
8 15
1 12
3 1
3 9
4 2
7 13
12 11
14 11
14 13
output
27
The first line of input contains integers N and M (\(N \le 300\,000\), \(3 \le M \le 10^{9}\)).
The following N lines contain two integers, starting point and destination for each villagers that want's
to travel today. These number will be in range 0 to M.
Output the minimum number of miles that Mirko must travel.
2 10
2 8
6 4
14
8 15
1 12
3 1
3 9
4 2
7 13
12 11
14 11
14 13
27