Bulbo

题意翻译

数轴上有一排（n个）灯，相邻的灯之间间隔为1。一开始你在一个初始位置，游戏共进行m轮，在每一轮开始之前，你可以选择花费|x-y|的代价从当前的x位置移动到y位置，每一轮游戏，区间[Li,Ri]的灯会亮起，你会付出min(dist(x,Pi))的代价，其中Pi为某个亮着的灯的位置。这一轮结束后，所有的灯泡再次熄灭。求整个过程的最小代价。 感谢@vanilla 提供的翻译

题目描述

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 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.

输入输出格式

输入格式

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 should contain a single number which represents the best result (minimum cost) that could be obtained by playing this Bulbo game.

输入输出样例

输入样例 #1

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

输出样例 #1

8

说明

Before 1. turn move to position 5 Before 2. turn move to position 9 Before 5. turn move to position 8