分数: 700 点
问题陈述
有 L 水平排列成一排的方块,已编号 1, 2, \ldots, L 从左到右。
在这些方块上是 N 企鹅,编号 1, 2, \ldots, N 从左到右。 最初,企鹅 i 已在广场上 A_i。 在这里, 1 \leq A_1 < A_2 < \ldots < A_N \leq L 成立。
您可以多次执行以下操作:
- 选择一只企鹅并将其向左或向右滑动。 只要前方有空的方块,企鹅就会一直滑行。 当它到达另一只企鹅占据的方格之前的方格时,或者前面没有方格时,它就会停止。
例如,假设 N=3, L=10,企鹅在方块上 (2,3,7)。 在这里,如果我们滑动企鹅 2 向右,它会移动到广场 6;如果我们滑动企鹅 3 向右,它会移动到广场 10.
你的目标是把企鹅 广场上的 i 广场上 B_i 对于每个 i。 在这里, 1 \leq B_1 < B_2 < \ldots < B_N \leq L 成立。 确定目标是否可以实现。如果可以实现,找出所需的最少操作数。
约束
- 1 \leq N \leq 10^5
- N \leq L \leq 10^9
- 1 \leq A_1 < A_2 < \ldots < A_N \leq L
- 1 \leq B_1 < B_2 < \ldots < B_N \leq L
- 输入的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
N L A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
输出
如果目标无法实现,请打印 -1;如果可以实现,请打印所需的最少操作数。
示例输入 1
4 11 3 4 6 10 1 5 6 11
示例输出 1
3
以下操作序列可实现目标:
- 幻灯片企鹅 1 到左边。企鹅现在在广场上 (1,4,6,10).
- 幻灯片企鹅 2 在右边。企鹅现在在广场上 (1,5,6,10).
- 幻灯片企鹅 4 在右边。企鹅现在在广场上 (1,5,6,11).
示例输入 2
1 3 1 2
示例输出 2
-1
示例输入 3
10 1000000000 65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792 1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000
示例输出 3
13