配点 : $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$ の壁を破壊して通過できるようになります。
• 高橋君はハンマーのある座標に着くとそこにあるハンマーを手に入れます。
• タイプ $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