Problem7262--ABC273 —— F - Hammer 2

7262: ABC273 —— F - Hammer 2

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

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 ii and get over it.
Determine if he can reach the goal. If he can, find the minimum distance he travels.

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.

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.

Sample 1 Input 

3 10
-2 8 -5
5 -10 3

Sample 1 Output 

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 2 Input 

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

Sample 2 Output 

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

Sample 3 Input 

1 100
30
60

Sample 3 Output 

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

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


4078987507

Source/Category

 
Submit