题目描述

数直線の原点に高橋君がいます。高橋君は座標 $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$ の壁を破壊して通過できるようになります。

高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君がゴールに到達することが可能であれば移動距離の最小値を整数として出力せよ。
不可能であれば -1 と出力せよ。

题目大意

有一个坐标轴，你一开始在 $0$ 坐标，你需要走到 $X$ 坐标， 但是在坐标轴上有 $N$ 堵墙，坐标为 $Y_i$，你不能跨越这堵墙除非你有能砸开这堵墙的锤子，第 $i$ 堵墙的锤子在 $Z_i$ 问你能不能走到 $X$ ，若能则输出最小的时间，否则输出 $-1$ 。

3 10
-2 8 -5
5 -10 3

40

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

1

1 100
30
60

-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$ は相異なる

Sample Explanation 1

以下の手順により、移動距離 $40$ で高橋くんがゴールに到達でき、これが移動距離の最小です。 - 座標 $0$ から高橋君が行動を開始する。 - 座標 $3$ に行く。タイプ $3$ のハンマーを手に入れる。 - 座標 $5$ に行く。タイプ $1$ のハンマーを手に入れる。 - 座標 $-2$ に行く。タイプ $1$ の壁を破壊する。 - 座標 $-5$ に行く。タイプ $3$ の壁を破壊する。 - 座標 $-10$ に行く。タイプ $2$ のハンマーを手に入れる。 - 座標 $8$ に行く。タイプ $2$ の壁を破壊する。 - 座標 $10$ に行く。ここがゴールである。

Sample Explanation 2

ゴールに移動するために、ハンマーを手に入れる必要も壁を破壊する必要もない場合もあります。

Sample Explanation 3

高橋君がタイプ $1$ のハンマーを手に入れることは不可能であり、ゴールに辿り着くこともできません。