## Bubble Cup V8 F Bulbo

View as PDF

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

Problem type

Bananistan is a beautiful banana republic. Beautiful women in beautiful dresses. Beautiful statues of beautiful warlords. Beautiful stars on 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 . Before each turn, the player can change his position with cost. After that, a contiguous set of bulbs lights up, and the 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 the number of turns and the initial position . The next lines contain two numbers and , which represent that all the bulbs from 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.

#### Sample Input

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

#### Sample Output

8

#### Explanation

Before , turn move to position . The movement cost is and the distance to the closest shining bulb is . The total cost is

Before , turn move to position . The movement cost is and the distance to the closest shining bulb is . The total cost is

Stay at position in turn and . The movement cost is and the distance to the closest shining bulb is also . The total cost is

Before , turn move to position . The movement cost is and the distance to the closest shining bulb is . The total cost is