Space Elevator

Time limit2sMemory limit1024 MB

Summary

Find the minimum total distance an elevator starting at height H0 must travel to carry every request from its pickup height u to its drop height v.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Intervals
Solved: No attempts yet

Problem

After years of material science research, scientists have finally devised a material strong enough to support the long-conceived space elevator!

The elevator is anchored to the Earth in geostationary orbit, which supports efficient vertical transportation through Earth's gravity well.

Significant amounts of engineering, time, and funding have gone into its construction, and the first shipments are now ready to launch! However, the scientists overlooked one major factor: the number of incoming requests they would receive!

In the first few minutes, requests came in from the National Space Agency to send water to the International Space Station (ISS), from the Intercollegiate Coalition for Planetary Comprehension (ICPC) to ship low-gravity probes assembled at the ISS, and from the Astronomy Department to launch a new high altitude satellite measuring solar flares. The local weather station also asked whether a lost high-altitude weather balloon could be retrieved on the way back.

To simplify the process, incoming requests will be aggregated and processed on a weekly basis. Time and energy loss depend almost entirely on the distance traveled, and factors like potential energy are nearly negligible.

The scientists asked the Computer Science departments at their local universities for a program that reads the requests for the week and finds the minimum vertical distance the elevator must travel to fulfill all of them.

The elevator has no capacity limit on how many packages it can hold at once, since requests to move particularly large objects are handled separately. The elevator can stop where it is as soon as it has fulfilled all of the requests, so the input also includes its starting location, where it stopped the previous week.

Input

The first line contains two integers $N$ and $H_0$ , the number of requests and the height the elevator is currently at, respectively ( $1 \leq N \leq 10^5$ ).

The next $N$ lines each contain two integers $u_i$ and $v_i$ , meaning there is a request to pick up something at height $u_i$ and drop it off at height $v_i$ . Docking procedures require high precision, so all heights are given as millimeters above sea level.

All heights satisfy $0 \le H_0, u_i, v_i \le 5 \cdot 10^{11}$ , and $u_i \neq v_i$ .

Output

Output the minimum distance (in millimeters) that the elevator must travel to fulfill all of the requests.

Examples3

Example 1
Input
```
1 40
30 60
```
Expected output
```
40
```
Example 2
Input
```
4 60
45 95
55 5
50 10
0 50
```
Expected output
```
155
```
Example 3
Input
```
4 80
100 60
10 20
85 95
55 10
```
Expected output
```
120
```