Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Bulbo

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBananistan 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 player at the position, which represents one of the bulbs. The distance between two neighboring bulbs is 1. Before each turn player can change his position with cost |*pos*_{new} - *pos*_{old}|. After that, a contiguous set of bulbs lights-up and player pays the cost that’s equal to the distance to 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

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 bulbs from interval [*l*_{start}, *l*_{end}] are shining this turn.

- 1 ≤
*n*≤ 5000 - 1 ≤
*x*≤ 10^{9} - 1 ≤
*l*_{start}≤*l*_{end}≤ 10^{9}

Output

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

Examples

Input

5 4

2 7

9 16

8 10

9 17

1 6

Output

8

Note

Before 1. turn move to position 5

Before 2. turn move to position 9

Before 5. turn move to position 8

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2019 02:45:25 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|