Leapfrog

時間制限 : 2 sec, メモリ制限 : 262144 KB

Leapfrog

Problem Statement

N 個のマスが円状に並んでいる。マスは時計回りに 1,\ 2,\ ... ,\ N と番号が振られている。各 i (1 ≤ i ≤ 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 ≤ N ≤ 3,000
  • 1 ≤ M ≤ N
  • 1 ≤ x_1<x_2< ... <x_M ≤ N
  • 1 ≤ y_1<y_2< ... <y_M ≤ 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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 2, Tokyo, Japan, 2015-09-12
http://acm-icpc.aitea.net/
http://jag2015summer-day2.contest.atcoder.jp/