## Bubble Cup V8 F Bulbo

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 . Before each turn player can change his position with 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 and initial position . Next lines contain two numbers and , which represent that all that 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.

#### Example Input

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

#### Example Output

8

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