锤子 2

题目描述

Takahashi 在数轴的原点处。Takahashi 想要到达坐标为 $X$ 的终点。

数轴上还有 $N$ 堵墙和 $N$ 把锤子。

在坐标 $Y_1,Y_2,\dots,Y_N$ 处分别有类型 $1,2,\dots,N$ 的墙。

最初,Takahashi 无法越过任何墙。

在坐标 $Z_1,Z_2,\dots,Z_N$ 处分别有类型 $1,2,\dots,N$ 的锤子。

当他到达某把锤子所在的坐标时,就会获得这把锤子。

类型 $i$ 的锤子专门用来摧毁类型 $i$ 的墙。获得类型 $i$ 的锤子后,他可以摧毁类型 $i$ 的墙并越过它。

判断他能否到达终点。如果能,求出他移动的最小距离。

输入格式

输入按以下格式从标准输入给出:

$N$ $X$
$Y_1$ $Y_2$ $\dots$ $Y_N$
$Z_1$ $Z_2$ $\dots$ $Z_N$

输出格式

如果 Takahashi 能到达终点,以整数形式输出他移动的最小可能距离。

否则,输出 -1。

样例

3 10
-2 8 -5
5 -10 3

40

Takahashi 可以按如下方式移动距离 $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

Takahashi 无法获得类型 $1$ 的锤子,也无法到达终点。

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

4078987507

数据范围

• 输入中的所有值均为整数。
• $1 \le N \le 1500$
• $1 \le |X|,|Y_i|,|Z_i| \le 10^9$
• $(2 \times N + 1)$ 个坐标 $X$、$Y_i$、$Z_i$ 两两不同。