题目描述

$X\ =\ 10^{100}$ として，各整数 $-X\ \leq\ i\ \leq\ X$ に対応する頂点があり，$-X\ \leq\ i\ \leq\ X-1$ について頂点 $i,\ i\ +\ 1$ を結ぶ無向辺 (以降，辺 $\{\ i,\ i\ +\ 1\ \}$ と呼ぶ) があるグラフがあります．

このグラフの辺は初めすべて赤く塗られています．また，$N$ 個 のコマがあり，$i$ 個目のコマは頂点 $a_i$ に置かれています．

maroon 君は次の操作を行うことができます．

• コマを $1$ つ選ぶ． このコマが頂点 $i$ にあるとき，コマを頂点 $i-1$ または頂点 $i+1$ に動かし，通った辺を，現在の色が赤なら青，青なら赤に塗り替える．

操作の過程で，同じ頂点に複数のコマが存在しても構いません．

maroon 君はこれから上記の操作を $0$ 回以上繰り返して，辺の色の組合せを目的の状態にしたいと思っています．目的の状態は 偶数 $K$ と，$K$ 個の整数 $t_1\ <\ t_2\ <\ \cdots\ <\ t_K$ で表され，$i\ <\ t_1$ について辺 $\{\ i,\ i\ +\ 1\ \}$ は赤，$t_1\ \leq\ i\ <\ t_2$ について辺 $\{\ i,\ i\ +\ 1\ \}$ は青，$\cdots,\ t_K\ \leq\ i$ について辺 $\{\ i,\ i\ +\ 1\ \}$ は赤 という状態です．より正確には，各奇数 $j\ =\ 1,\ 3,\ \cdots,\ K-1$ に対して，$t_j\ \leq\ i\ <\ t_{j+1}$ を満たす $i$ について辺 $\{\ i,\ i\ +\ 1\ \}$ は青で，それ以外の辺はすべて赤です．

maroon 君が辺の色の組合せを目的の状態にするために必要な操作回数の最小値を求めてください．また，そのような操作が不可能であるなら $-1$ を出力してください．

输入格式

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

$N$ $K$ $a_1$ $a_2$ $\cdots$ $a_N$ $t_1$ $t_2$ $\cdots$ $t_K$

输出格式

maroon 君が辺の色の組合せを目的の状態にするために必要な操作回数の最小値を出力せよ．また，そのような操作が不可能であるなら $-1$ を出力せよ．

题目大意

设 $X=10{^{100}}$。现在有一张节点编号从 $-X$ 到 $X$ 的图，点 $i$ 到点 $i+1(-X\leq i\leq X-1)$ 之间有一条无向边，初始时所有边都是红色的。

有 $N$ 个棋子在这张图上，其中第 $i$ 个在点 $a{_i}$ 上。

Maroon 可以重复以下操作：

• 选择一个棋子 $i$，将它移动到 $a{_{i}}-1$ 或 $a{_{i}}+1$ 上，并把它所经过的边由红色染成蓝色，如果经过的边是蓝色的，那就染成红色。

Maroon 想把这张图染成他想要的颜色组合。他会给出 $K$ 个数字 $t{_1}$ 到 $t{_K}$（保证严格单调递增且 $K$ 为偶数），意思是将节点 $t{_1}$ 左边的边染成红色，$t{_1}$ 到 $t{_2}$ 之间的边染成蓝色……以此类推，最后把 $t{_K}$ 右边的边染成红色。

求出达到要求的最少的操作次数，如果无解，输出 -1。

2 2
2 -1
-2 2

4

2 2
2 2
5 8

9

3 4
1 3 5
0 2 4 6

-1

4 4
3 4 5 6
3 4 5 6

2

提示

制約

• $1\ \leq\ N\ \leq\ 5000$
• $2\ \leq\ K\ \leq\ 5000$
• $K$ は偶数
• $|a_i|\ \leq\ 10^9$
• $|t_i|\ \leq\ 10^9$
• $t_i\ <\ t_{i+1}$
• 入力は全て整数

Sample Explanation 1

例えば以下のように $4$ 回の操作で目的の状態にでき，$4$ 本の辺の色を変える必要があるのでこれが最適です． これは初めの状態です．便宜上 $-3$ より左と $3$ より右の辺は省いています．  $-1$ にあるコマを $-2$ に動かすと次の状態になります．  $2$ にあるコマを $1$ に動かすと次の状態になります．  $1$ にあるコマを $0$ に動かすと次の状態になります．  $0$ にあるコマを $-1$ に動かすと次の状態になり，これが目的の状態です． 

Sample Explanation 2

初めから同じ頂点に複数のコマがある場合もあります．