AT_abc273_f [ABC273F] Hammer 2

题目描述

高桥君现在在数轴的原点。他想移动到坐标 $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$。

输入输出样例 #1

输入 #1

3 10
-2 8 -5
5 -10 3

输出 #1

40

输入输出样例 #2

输入 #2

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

输出 #2

1

输入输出样例 #3

输入 #3

1 100
30
60

输出 #3

-1

输入输出样例 #4

输入 #4

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

输出 #4

4078987507

说明/提示

限制条件

• 所有输入均为整数。
• $1\leq N\leq 1500$
• $1\leq |X|,|Y_i|,|Z_i|\leq 10^9$
• 总共 $2\times N+1$ 个坐标 $X,Y_i,Z_i$ 互不相同。

样例解释 1

按照以下步骤，高桥君可以以 $40$ 的最小移动距离到达终点：

• 从坐标 $0$ 开始。
• 移动到坐标 $3$，获得类型 $3$ 的锤子。
• 移动到坐标 $5$，获得类型 $1$ 的锤子。
• 移动到坐标 $-2$，破坏类型 $1$ 的墙。
• 移动到坐标 $-5$，破坏类型 $3$ 的墙。
• 移动到坐标 $-10$，获得类型 $2$ 的锤子。
• 移动到坐标 $8$，破坏类型 $2$ 的墙。
• 移动到坐标 $10$，到达终点。

样例解释 2

有时不需要获得任何锤子或破坏任何墙就能到达终点。

样例解释 3

高桥君无法获得类型 $1$ 的锤子，因此也无法到达终点。

由 ChatGPT 4.1 翻译