← 返回题目列表

AtCoder · icpc2015summer_day2_k

K. 蛙跳

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

问题陈述

N 正方形排列成圆形。顺时针方格 它的编号为 1,\ 2,\ ...,\ 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