2456 - DS_2021_Quiz5_Sort Scoreboard

Time

2021/12/22 18:30:00 2021/12/22 20:00:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
13401 DS_2021_Quiz5_Sort

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. 1 ≤ N ≤ 50,0000
  2. 0 ≤ Si, EiM ≤ 109

Output

Print the minimum total distance required.

A newline is added after the minimum total distance.

Sample Input  Download

Sample Output  Download

Tags

TS{iinlnf};TS{Bnn}; >n;NTL h=R(1n) w(h)NTB r=h.r <r.i;P(l)P(r);h=h.n P{i(r)<r.iP(l)P(r)} R{NTL h,t i(l-r)h=m r h for(l≤r) NTLl=R(l,i-1) NTLr=R(i+1,r) w(l)ri=rw(ri)ri=ri.n l=l.n NTB NTL not h t=l h=l t.n=l t=l



Discuss