102735: [AtCoder]ABC273 F - Hammer 2
Description
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
Input
题意翻译
有一个坐标轴，你一开始在 $0$ 坐标，你需要走到 $X$ 坐标， 但是在坐标轴上有 $N$ 堵墙，坐标为 $Y_i$，你不能跨越这堵墙除非你有能砸开这堵墙的锤子，第 $i$ 堵墙的锤子在 $Z_i$ 问你能不能走到 $X$ ，若能则输出最小的时间，否则输出 $-1$ 。Output
问题描述
高桥在数轴的原点处。高桥想要到达坐标为$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$
- 坐标$X,Y_i$和$Z_i$的$(2 \times N + 1)$个值是不同的。
输入
输入将从标准输入中以以下格式给出：
$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