← 返回题目列表

AtCoder · arc114_d

D. 在线移动棋子

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

分数: 600 点

问题陈述

让 X = 10^{100}。我们有一个图,每个整数都有一个顶点 -X \leq i \leq X,以及连接 Vertex 的无向边 i 和顶点 i + 1 (我们将其称为 Edge \{ i, i + 1 \})对于每个 -X \leq i \leq X-1.

该图中的所有边最初都漆成红色。 此外,我们还有 N 件,以及 i- 其中第一个位于 Vertex a_i.

Maroon可以重复以下操作:

  • 选择一块。如果该棋子在顶点上 i,将其移动到顶点 i-1 或顶点 i + 1。然后,如果遍历的边现在被漆成红色,则将其重新漆成蓝色,反之亦然。

在此过程中,同一顶点上可能存在多个碎片。

Maroon 想要执行此操作零次或多次,以使边缘绘制成他想要的颜色组合。所需的颜色组合由偶数表示 K 和 K 整数 t_1 < t_2 < \cdots < t_K:这意味着 Edge \{ i, i + 1 \} 为红色 i < t_1,蓝色为 t_1 \leq i < t_2, \cdots,红色代表 t_K \leq i。更正式地说,对于每个奇数 j = 1, 3, \cdots, K-1,边缘 \{ i, i + 1 \} 为蓝色 i 这样 t_j \leq i < t_{j+1};所有其他边缘都是红色的。

求出将边缘绘制为所需颜色组合所需的最少操作数。如果无法做到这一点,请打印 -1.

约束

  • 1 \leq N \leq 5000
  • 2 \leq K \leq 5000
  • K 是偶数。
  • |a_i| \leq 10^9
  • |t_i| \leq 10^9
  • t_i < t_{i+1}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
a_1 a_2 \cdots a_N
t_1 t_2 \cdots t_K

输出

打印将边缘绘制为所需颜色组合所需的最少操作数。如果无法做到这一点,请打印 -1.


示例输入 1

2 2
2 -1
-2 2

示例输出 1

4

如下所示,我们可以通过四次操作达到所需的状态,这是最佳的,因为我们需要重新绘制四个边。

以下是初始情况。为了方便起见,我们省略了左侧的边 -3 和权利 3.

0

我们继续前进 -1 to -2 获得以下信息:

1

然后,我们继续移动该块 2 to 1 获得以下信息:

2

然后,我们继续移动该块 1 to 0 获得以下信息:

3

然后,我们继续移动该块 0 to -1 得到以下结果,这是所需的状态:

last


示例输入 2

2 2
2 2
5 8

示例输出 2

9

一开始就可以在同一顶点上有多个片段。


示例输入 3

3 4
1 3 5
0 2 4 6

示例输出 3

-1

示例输入 4

4 4
3 4 5 6
3 4 5 6

示例输出 4

2