← 返回题目列表

AtCoder · agc048_c

C. 企鹅滑冰

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

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