AT_arc114_d.[ARC114D] Moving Pieces on Line

设 $X = 10^{100}$，对于每个整数 $-X \leq i \leq X$，有一个对应的顶点。对于每个 $-X \leq i \leq X-1$，存在一条连接顶点 $i$ 和 $i+1$ 的无向边（下文称为边 $\{i, i+1\}$）的图。

该图的所有边初始时都被涂成红色。现在有 $N$ 个棋子，第 $i$ 个棋子被放置在顶点 $a_i$ 上。

maroon 君可以进行如下操作：

• 选择一个棋子。若该棋子当前在顶点 $i$，则可以将其移动到顶点 $i-1$ 或 $i+1$，并将经过的那条边的颜色反转（如果当前为红色则变为蓝色，蓝色则变为红色）。

在操作过程中，允许多个棋子位于同一个顶点。

maroon 君希望通过若干次上述操作（可以为零次），使得边的颜色组合达到目标状态。目标状态由一个偶数 $K$ 和 $K$ 个整数 $t_1 < t_2 < \cdots < t_K$ 给出，具体要求如下：

• 对于 $i < t_1$ 的所有 $i$，边 $\{i, i+1\}$ 为红色；
• 对于 $t_1 \leq i < t_2$ 的所有 $i$，边 $\{i, i+1\}$ 为蓝色；
• 对于 $t_2 \leq i < t_3$ 的所有 $i$，边 $\{i, i+1\}$ 为红色；
• 以此类推，对于每个奇数 $j = 1, 3, \cdots, K-1$，$t_j \leq i < t_{j+1}$ 的边为蓝色，其余边为红色。

请你求出 maroon 君将边的颜色组合变为目标状态所需的最小操作次数。如果无法实现目标状态，则输出 $-1$。

输入通过标准输入给出，格式如下：

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

请输出 maroon 君将边的颜色组合变为目标状态所需的最小操作次数。如果无法实现目标状态，则输出 $-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}$
• 输入均为整数

样例解释 1

例如，可以通过 $4$ 次操作达到目标状态，需要改变 $4$ 条边的颜色，这是最优解。初始状态如下（为方便起见，省略了 $-3$ 左侧和 $3$ 右侧的边）：

将 $-1$ 处的棋子移动到 $-2$，状态变为：

将 $2$ 处的棋子移动到 $1$，状态变为：

将 $1$ 处的棋子移动到 $0$，状态变为：

将 $0$ 处的棋子移动到 $-1$，状态变为目标状态：

样例解释 2

初始时也可能有多个棋子在同一个顶点。

由 ChatGPT 4.1 翻译