MOG Round #1Ended |
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. Fito lives in the village marked with $0$. He is in the business of transporting people between villages with his boat. Today, Fito 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. Fito'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$. Fito 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 Fito must travel in order to transport everyone to their destinations and reach village $M$ at the end.
The first line of input contains integers $N$ and $M$ $(N \leq 300 000, 3 \leq M \leq 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 Fito must travel.