/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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 を出力してください．
制約
- 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}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N K a_1 a_2 \cdots a_N t_1 t_2 \cdots t_K
出力
maroon 君が辺の色の組合せを目的の状態にするために必要な操作回数の最小値を出力せよ．また，そのような操作が不可能であるなら -1 を出力せよ．
入力例 1
2 2 2 -1 -2 2
出力例 1
4
例えば以下のように 4 回の操作で目的の状態にでき，4 本の辺の色を変える必要があるのでこれが最適です．
これは初めの状態です．便宜上 -3 より左と 3 より右の辺は省いています．
-1 にあるコマを -2 に動かすと次の状態になります．
2 にあるコマを 1 に動かすと次の状態になります．
1 にあるコマを 0 に動かすと次の状態になります．
0 にあるコマを -1 に動かすと次の状態になり，これが目的の状態です．
入力例 2
2 2 2 2 5 8
出力例 2
9
初めから同じ頂点に複数のコマがある場合もあります．
入力例 3
3 4 1 3 5 0 2 4 6
出力例 3
-1
入力例 4
4 4 3 4 5 6 3 4 5 6
出力例 4
2
Score : 600 points
Problem Statement
Let X = 10^{100}. We have a graph with a vertex for each integer -X \leq i \leq X, and an undirected edge connecting Vertex i and Vertex i + 1 (we will call it Edge \{ i, i + 1 \}) for each -X \leq i \leq X-1.
All edges in this graph are initially painted red. Additionally, we have N pieces, and the i-th of them is on Vertex a_i.
Maroon can repeat the following operation:
- Choose a piece. If that piece is on Vertex i, move it to Vertex i-1 or Vertex i + 1. Then, if the traversed edge is now painted red, repaint it blue, and vice versa.
During the process, there may be multiple pieces on the same vertex.
Maroon wants to do this operation zero or more times to make the edges painted in his desired combination of colors. The desired combination of colors is represented by an even number K and K integers t_1 < t_2 < \cdots < t_K: it means that Edge \{ i, i + 1 \} is red for i < t_1, blue for t_1 \leq i < t_2, \cdots, red for t_K \leq i. More formally, for each odd number j = 1, 3, \cdots, K-1, Edge \{ i, i + 1 \} is blue for each i such that t_j \leq i < t_{j+1}; all other edges are red.
Find the minimum number of operations required to make the edges painted in the desired combination of colors. If it is impossible to do so, print -1.
Constraints
- 1 \leq N \leq 5000
- 2 \leq K \leq 5000
- K is even.
- |a_i| \leq 10^9
- |t_i| \leq 10^9
- t_i < t_{i+1}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K a_1 a_2 \cdots a_N t_1 t_2 \cdots t_K
Output
Print the minimum number of operations required to make the edges painted in the desired combination of colors. If it is impossible to do so, print -1.
Sample Input 1
2 2 2 -1 -2 2
Sample Output 1
4
As shown below, we can achieve the desired state in four operations, which is optimal since we need to repaint four edges.
The following is the initial situation. For convenience, we have omitted edges to the left of -3 and the right of 3.
We move the piece on -1 to -2 to get the following:
Then, we move the piece on 2 to 1 to get the following:
Then, we move the piece on 1 to 0 to get the following:
Then, we move the piece on 0 to -1 to get the following, which is the desired state:
Sample Input 2
2 2 2 2 5 8
Sample Output 2
9
There can be multiple pieces on the same vertex already in the beginning.
Sample Input 3
3 4 1 3 5 0 2 4 6
Sample Output 3
-1
Sample Input 4
4 4 3 4 5 6 3 4 5 6
Sample Output 4
2