AquaMoon and Time Stop (easy version)

题意翻译

### 题目描述 一个人走在步行街上。在时刻 $0$ 时，他位于坐标 $x$，并以每秒 $1$ 单位的速度移动。这个人受到了鬼的 $n$ 次诅咒，第 $i$ 次诅咒从 $tl_i-1+10^{-18}$ 开始，到 $tr_i+1-10^{-18}$ 结束（**不包含两端**），如果他走到了 $(l_i-1+10^{-18},r_i+1-10^{-18})$ 之间的位置，他就会死亡。为了拯救这个人，你可以可以在任意时刻 $t$ 停止时间，然后将他从当前坐标 $x$ 移动到任意坐标 $y$（**$t$、$x$ 和 $y$ 不一定是整数**），消耗了你 $\vert x-y\vert$ 能量。**注意：移动是连续的，所以如果在时间 $t$ 的点 $x$ 和点 $y$ 之间存在一段诅咒区域，那么这个人也会死亡。** 那么你最少要消耗多少能量呢？ ### 输入格式 - 第一行包含一个整数 $n$，表示诅咒的次数。 - 第二行包含一个整数 $x$，表示此人的初始坐标。 - 以下 $n$ 行，每行四个整数 $tl_i$, $tr_i$，$l_i$，$r_i$，含义如题中所示。 ### 输出格式 输出一个整数，表示你需要消耗的最小能量，四舍五入到整数。 ### 说明/提示 对于 $100\%$ 的数据，$1 \le n \le 2\times 10^3$，$1 \le x \le 10^6$，$1\le tl_i\le tr_i\le 10^6$，$1\le l_i\le r_i\le 10^6$。

题目描述

Note that the differences between easy and hard versions are the constraints on $ n $ and the time limit. You can make hacks only if both versions are solved. AquaMoon knew through foresight that some ghosts wanted to curse tourists on a pedestrian street. But unfortunately, this time, these ghosts were hiding in a barrier, and she couldn't enter this barrier in a short time and destroy them. Therefore, all that can be done is to save any unfortunate person on the street from the ghosts. The pedestrian street can be represented as a one-dimensional coordinate system. There is one person hanging out on the pedestrian street. At the time $ 0 $ he is at coordinate $ x $ , moving with a speed of $ 1 $ unit per second. In particular, at time $ i $ the person will be at coordinate $ x+i $ . The ghosts are going to cast $ n $ curses on the street. The $ i $ -th curse will last from time $ tl_i-1+10^{-18} $ to time $ tr_i+1-10^{-18} $ (exclusively) and will kill people with coordinates from $ l_i-1+10^{-18} $ to $ r_i+1-10^{-18} $ (exclusively). Formally that means, that the person, whose coordinate is between $ (l_i-1+10^{-18},r_i+1-10^{-18}) $ in the time range $ (tl_i-1+10^{-18},tr_i+1-10^{-18}) $ will die. To save the person on the street, AquaMoon can stop time at any moment $ t $ , and then move the person from his current coordinate $ x $ to any coordinate $ y $ ( $ t $ , $ x $ and $ y $ are not necessarily integers). The movement costs AquaMoon $ |x-y| $ energy. The movement is continuous, so if there exists some cursed area between points $ x $ and $ y $ at time $ t $ , the person will die too. AquaMoon wants to know what is the minimum amount of energy she needs to spend in order to save the person on the street from all $ n $ curses. But she is not good at programming. As her friend, can you help her?

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1\le n\le 2000 $ ) — the number of curses. The next line contains a single integer $ x $ ( $ 1\le x\le 10^6 $ ) — the initial coordinate of the person. The following $ n $ lines contain four integers $ tl_i $ , $ tr_i $ , $ l_i $ , $ r_i $ each ( $ 1\le tl_i\le tr_i\le 10^6 $ , $ 1\le l_i\le r_i\le 10^6 $ ).

输出格式

Print a single integer — the minimum energy which AquaMoon needs to spent, rounded up to the nearest integer (in case there are two nearest integers you should round the answer to the highest of them).

输入输出样例

输入样例 #1

2
1
1 2 1 2
2 3 2 3

输出样例 #1

2

输入样例 #2

3
4
1 4 1 2
1 4 4 15
6 7 1 4

输出样例 #2

8

输入样例 #3

4
3
1 5 1 1
4 10 1 4
1 2 3 13
1 10 7 19

输出样例 #3

14

输入样例 #4

7
5
78 96 76 91
6 16 18 37
53 63 40 56
83 88 21 38
72 75 17 24
63 63 53 60
34 46 60 60

输出样例 #4

20