← 返回题目列表

AtCoder · abc273_f

I. 锤子2

中文机器翻译题面 查看原题

分数: 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

输出

如果 Takahashi 可以到达目标,则以整数形式打印他可能行进的最短距离。
否则,打印 -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