题目描述

有 $N$ 个格子按照环形排列。每个格子从 $1$ 到 $N$ 编号。对于每个 $i$ ($1\\leq i\\leq N-1$)，第 $i$ 个格子和第 $i+1$ 个格子相邻。此外，第 $N$ 个格子和第 $1$ 个格子相邻。

其中的 $M$ 个格子中，放有 $1$ 个无法区分的棋子。开始时，棋子放在第 $x_1,\\ x_2,\\ ...,\\ x_M$ 个格子上。我们希望通过若干次操作，使得棋子被放在第 $y_1,\\ y_2,\\ ...,\\ y_M$ 个格子上。

• 选择连续的顺时针或逆时针方向的 $3$ 个格子，依次标记为 $A,\\ B,\\ C$。如果 $A$ 和 $B$ 上有棋子而 $C$ 上没有棋子，则将 $A$ 上的棋子移动到 $C$ 上。

判断是否可以将棋子放在第 $y_1,\\ y_2,\\ ...,\\ y_M$ 个格子上。如果可以，求出所需操作的最小次数。

约束条件

• $3\\leq N\\leq 3,000$
• $1\\leq M\\leq N$
• $1\\leq x_1<x_2<...<x_M\\leq N$
• $1\\leq y_1<y_2<...<y_M\\leq N$

输入格式

输入从标准输入读入，具有以下格式。

$N$ $M$ $x_1$ $x_2$ $...$ $x_M$ $y_1$ $y_2$ $...$ $y_M$

输出格式

如果可以将棋子放在第 $y_1,\\ y_2,\\ ...,\\ y_M$ 个格子上，则输出所需操作的最小次数。否则，输出 -1。

示例输入 1

7 2
1 2
5 6

示例输出 1

3

可以通过以下 $3$ 次操作实现：

• 将第 $2$ 个格子的棋子移动到第 $7$ 个格子。
• 将第 $1$ 个格子的棋子移动到第 $6$ 个格子。
• 将第 $7$ 个格子的棋子移动到第 $5$ 个格子。

示例输入 2

3 1
1
2

示例输出 2

-1

示例输入 3

2999 3
1 2 3
2 3 4

示例输出 3

4491004