请注意,简单版和困难版之间的区别在于 $$$n$$$ 的限制和时间限制。只有两个版本都解决了,你才能进行黑客攻击。
水月有先见之明,知道有鬼魂想要在步行街上诅咒游客。但可惜的是,这一次,这些鬼魂都隐藏在结界之中,她无法短时间内进入这个结界,将它们消灭掉。因此,我们能做的就是从鬼魂手中拯救街上任何不幸的人。
步行街可以表示为一维坐标系。步行街上有一个人闲逛。此时$$$0$$$他位于坐标$$$x$$$处,以每秒$$$1$$$单位的速度移动。特别是,在时间 $$$i$$$ 时,该人将位于坐标 $$$x+i$$$ 处。
鬼魂将在街上施放 $$$n$$$ 诅咒。第 $$$i$$$ 诅咒将从 $$$tl_i-1+10^{-18}$$$ 持续到 $$$tr_i+1-10^{-18}$$$(仅),并且会杀死坐标从 $$$l_i-1+10^{-18}$$$ 到 $$$r_i+1-10^{-18}$$$(仅)的人。从形式上来说,这意味着,在 $$$(tl_i-1+10^{-18},tr_i+1-10^{-18})$$$ 时间范围内坐标位于 $$$(l_i-1+10^{-18},r_i+1-10^{-18})$$$ 之间的人将会死亡。
为了拯救街上的人,AquaMoon可以随时停止时间$$$t$$$,然后将人从当前坐标$$$x$$$移动到任意坐标$$$y$$$($$$t$$$、$$$x$$$和$$$y$$$不一定是整数)。该运动会消耗 AquaMoon $$$|x-y|$$$ 能量。运动是连续的,所以如果在$$$t$$$时刻$$$x$$$和$$$y$$$之间存在一些诅咒区域,这个人也会死。
AquaMoon 想知道她需要花费多少能量才能将街上的人从所有 $$$n$$$ 诅咒中拯救出来。但她不擅长编程。作为她的朋友,你能帮助她吗?
输入
第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2000$$$) — 诅咒的数量。
下一行包含一个整数 $$$x$$$ ($$$1\le x\le 10^6$$$) — 人的初始坐标。
以下 $$$n$$$ 行包含四个整数 $$$tl_i$$$、$$$tr_i$$$、$$$l_i$$$、$$$r_i$$$ ($$$1\le tl_i\le tr_i\le 10^6$$$、$$$1\le l_i\le r_i\le 10^6$$$)。
输出
打印一个整数 - AquaMoon 需要消耗的最小能量,四舍五入到最接近的整数(如果有两个最接近的整数,您应该将答案四舍五入到其中最高的整数)。
示例
输入 #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