F - Hammer 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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 と出力せよ。

入力例 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

Score : 500 points

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

  • At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
    • Initially, Takahashi cannot get over the walls.
  • At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
    • When he arrives at a coordinate with a hammer, he obtains the hammer.
    • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

  • All values in the input are integers.
  • 1 \le N \le 1500
  • 1 \le |X|,|Y_i|,|Z_i| \le 10^9
  • The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Input

The input is given from Standard Input in the following format:

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

Output

If Takahashi can reach the goal, print the minimum possible distance he travels as an integer.
Otherwise, print -1.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

  • He starts at coordinate 0.
  • He moves to coordinate 3 to obtain the hammer of type 3.
  • He moves to coordinate 5 to obtain the hammer of type 1.
  • He moves to coordinate -2 to destroy the wall of type 1.
  • He moves to coordinate -5 to destroy the wall of type 3.
  • He moves to coordinate -10 to obtain the hammer of type 2.
  • He moves to coordinate 8 to destroy the wall of type 2.
  • He moves to coordinate 10, which is the goal.

Sample Input 2

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

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

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

Sample Output 4

4078987507