当前没有测试数据。

F - 铁锤 2

得分：$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$

输出

如果高滨可以到达终点，输出他行进的最小距离作为一个整数。
否则，输出 -1。

3 10
-2 8 -5
5 -10 3

40

高滨可以按照最小距离 $40$ 到达终点，如下所示：

• 他从坐标 $0$ 开始。
• 他移动到坐标 $3$，获得第 $3$ 类锤子。
• 他移动到坐标 $5$，获得第 $1$ 类锤子。
• 他移动到坐标 $-2$，摧毁第 $1$ 类墙。
• 他移动到坐标 $-5$，摧毁第 $3$ 类墙。
• 他移动到坐标 $-10$，获得第 $2$ 类锤子。
• 他移动到坐标 $8$，摧毁第 $2$ 类墙。
• 他移动到坐标 $10$，终点。

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

1

不一定要获得锤子或摧毁墙才能到达终点。

1 100
30
60

-1

高滨无法获得第 $1$ 类锤子，也无法到达终点。

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

4078987507