Bubble Cup V8 F Bulbo

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 64M

Problem type

Bananistan is a beautiful banana republic. Beautiful women in beautiful dresses. Beautiful statues of beautiful warlords. Beautiful stars in beautiful nights.

In Bananistan people play this crazy game – Bulbo. There’s an array of bulbs and each player has a position, which represents one of the bulbs. Distance between two neighboring bulbs is 1. Before each turn player can change his position with |pos_{new} - pos_{old}| cost. After that, a contiguous set of bulbs lights-up, and player pays the cost that’s equal to the distance from the closest shining bulb. Then all bulbs go dark again. The goal is to minimize your summed cost. I tell you, Bananistanians are spending their nights playing with bulbs.

Banana day is approaching, and you are hired to play the most beautiful Bulbo game ever. A huge array of bulbs is installed, and you know your initial position and all the light-ups in advance. You need to play the ideal game and impress Bananistanians, and their families.

Input Specification

The first line contains number of turns n and initial position x. Next n lines contain two numbers l_{start} and l_{end}, which represent that all that bulbs from [l_{start}, l_{end}] interval are shining this turn.

Output Specification

Output should contain a single number which represents the best result (minimum cost) that could be obtained by playing this Bulbo game.

Constraints

  • 1 \le n \le 5000
  • 1 \le x \le 10^9
  • 1 \le l_{start} \le l_{end} \le 10^9

Example Input

5 4
2 7
9 16
8 10
9 17
1 6

Example Output

8

Before 1. turn move to position 5. The movement cost is |4 - 5| = 1 and the distance to the closest shining bulb is 0. The total cost is 1

Before 2. turn move to position 9. The movement cost is |5 - 9| = 4 and the distance to the closest shining bulb is 0. The total cost is 1 + 4 = 5

Stay at position 9 in turn 3 and 4. The movement cost is 0 and the distance to the closest shining bulb is also 0. The total cost is 1 + 4 = 5

Before 5. turn move to position 8. The movement cost is |9 - 8| = 1 and the distance to the closest shining bulb is 2. The total cost is 1 + 4 + 1 + 2 = 8


Comments

There are no comments at the moment.