分数: 500 点
问题陈述
高桥位于数轴的原点。 高桥想要在坐标上达到目标 X.
此外,还有 N 墙壁和 N 锤子在数轴上。
- 在坐标处 Y_1,Y_2,\dots,Y_N 是类型的墙
分别是 1,2,\dots,N。
- 最初,高桥无法翻墙。
- 在坐标处 Z_1,Z_2,\dots,Z_N 是类型的锤子 1,2,\dots,N。
- 当他到达有锤子的坐标时,他获得了锤子。
- 锤子类型 i 致力于破坏墙壁类型 i。 当他获得了类型之锤之后 i,他可以破坏类型的墙 i 并克服它。
确定他是否能够达到目标。 如果可以的话,求他行驶的最短距离。
约束
- 输入中的所有值都是整数。
- 1 \le N \le 1500
- 1 \le |X|,|Y_i|,|Z_i| \le 10^9
- 的 (2 \times N + 1) 坐标 X,Y_i 和 Z_i 是不同的。
输入
输入由标准输入按以下格式给出:
N X Y_1 Y_2 \dots Y_N Z_1 Z_2 \dots Z_N
输出
如果 Takahashi 可以到达目标,则以整数形式打印他可能行进的最短距离。
否则,打印 -1.
示例输入 1
3 10 -2 8 -5 5 -10 3
示例输出 1
40
高桥可以通过移动距离达到目标 40 如下,这是可能的最小值:
- 他从坐标开始 0.
- 他移动到坐标 3 获得锤子类型 3.
- 他移动到坐标 5 获得锤子类型 1.
- 他移动到坐标 -2 破坏墙壁类型 1.
- 他移动到坐标 -5 破坏墙壁类型 3.
- 他移动到坐标 -10 获得锤子类型 2.
- 他移动到坐标 8 破坏墙壁类型 2.
- 他移动到坐标 10,这是目标。
示例输入 2
5 -1 10 -20 30 -40 50 -10 20 -30 40 -50
示例输出 2
1
他可能不需要获得锤子或摧毁墙壁来达到目标。
示例输入 3
1 100 30 60
示例输出 3
-1
高桥无法获得该类型的锤子 1,他也无法达到目标。
示例输入 4
4 865942261 703164879 -531670946 -874856231 -700164975 -941120316 599462305 -649785130 665402307
示例输出 4
4078987507