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

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

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

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

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

示例输入 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