# | Problem | Pass Rate (passed user / total user) |
---|---|---|
13401 | DS_2021_Quiz5_Sort |
|
Description
In this quiz, you need to simulate a goods transport problem.
There exist N goods to be transported. For any good Gi, it should be transported from Si to Ei. A truck delivers these goods from position 0 and must return to position M at last. Unfortunately, this truck can only transport one good at a time. Please help the driver to find out the minimum total distance.
For example,
2 10 // Number of goods = 2, road length = 10 (i.e., the truck must arrive at location 10 at the very end)
0 9 // S1 = 0 and E1 = 9
6 5 // S2 = 6 and E2 = 5
The truck always starts at location 0. The truck first loads good G1 at location 0 and transports G1 to position 6 (and unload G1). Then, it loads G2, and then transports G2 to position 5. Next, we can go to position 6 to pick up G1 and transport it to position 9. Note that the truck must arrive 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 goods and the terminal position, respectively.
The next N lines, each contains 2 integers Si, Ei which denote the start position and end position of good Gi, respectively.
Please note:
- 1 ≤ N ≤ 50,0000
- 0 ≤ Si, Ei ≤ M ≤ 109
Output
Print the minimum total distance required.
A newline is added after the minimum total distance.