K - Leapfrog Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

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 とおく。AB にそれぞれ駒があり C に駒がないならば、A の駒を C へ移動する。

y_1,\ y_2,\ ...,\ y_M 番目のマスに駒が置かれているようにできるか判定せよ。できるならば、必要な操作の回数の最小値を求めよ。

Constraints

  • 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

Input Format

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

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

Output Format

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


Sample Input 1

7 2
1 2
5 6

Sample Output 1

3

次のように 3 回の操作を行えばよい。

  • 2 番目のマスの駒を 7 番目のマスへ移動する。
  • 1 番目のマスの駒を 6 番目のマスへ移動する。
  • 7 番目のマスの駒を 5 番目のマスへ移動する。

Sample Input 2

3 1
1
2

Sample Output 2

-1

Sample Input 3

2999 3
1 2 3
2 3 4

Sample Output 3

4491004