22420번 - Leapfrog 다국어

$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$ 番目のマスに駒が置かれているようにできるか判定せよ。できるならば、必要な操作の回数の最小値を求めよ。

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$x_1$ $x_2$ $...$ $x_M$

$y_1$ $y_2$ $...$ $y_M$

$y_1,\ y_2,\ ...,\ y_M$ 番目のマスに駒が置かれているようにできるならば、必要な操作の回数の最小値を一行に出力せよ。できないならば、代わりに -1 を一行に出力せよ。

• $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$