AT_tenka1_2015_final_c 天下一不正

[problemUrl]: https://atcoder.jp/contests/tenka1-2015-final/tasks/tenka1_2015_final_c サワくんは天下一プログラマーコンテスト 1998 の本戦後に行われる懇親会の余興のためにあみだくじを作りました。 しかし、オカモトくんはそのあみだくじをこっそり改竄かいざんし、結果全体を操作することにしました。 オカモトくんは望む結果を得るために、あみだくじに好きなだけ横線を足すことが出来ます。 しかし、改竄かいざんに長い時間を使ってしまえば、サワくんに発覚するおそれがあります。そのため最小の本数を事前に計算することにしました。 ただし、横線は縦線をまたぐことができず、複数の横線がまったく同じ高さになることは出来ないものとし、また全ての横線は水平でなければいけません。

入力は以下の形式で標準入力から与えられる。 > $ W $ $ H $ $ a_0 $ $ a_1 $ $ a_2 $ ... $ a_{H-1} $ $ b_0 $ $ b_1 $ $ b_2 $ ... $ b_{W-1} $ - 縦線の本数を表す $ W\ (3\ \leq{}\ W\ \leq{}\ 7) $ と既に書き込まれた横線の本数を表す $ H\ (0\ \leq{}\ H\ \leq{}\ 100,000) $ が $ 1 $ 行目に与えられる。 - $ 2 $ 行目には既に書き込まれている上から $ n $ 本目の横線の左側の端点が接する縦線の位置 $ a_n\ (0\ \leq{}\ a_n\ \leq{}\ W-2) $ が与えられる。 - $ 3 $ 行目には改竄かいざん結果が与えられる。左から $ b_{m}\ (0\ \leq{}\ b_{m}\ \leq{}\ W\ -\ 1) $ 番目の縦線の上端が、左から $ m $ 番目の縦線の下端に繋がることがオカモトくんの望みである。 ### 出力 改竄に必要な最小本数を1行で出力せよ。出力の末尾には改行を入れること。

N/A

### 配点 この問題には部分点が設定されている。 - $ H\ \leq{}\ 100 $ を満たすテストケース全てに正解した場合は、$ 45 $ 点が与えられる。 - 全てのテストケースに正解した場合は、上記とは別に $ 105 $ 点が与えられる。 ### Sample Explanation 1 \### 出力例1 ``` ```

1
```

サワくんが作成したあみだくじは下記のようになります。

 ```

0 1 2
| | |
+-+ |
| | |
| | |
1 0 2
```

$ 1 $ 本の横線を書き足すことでオカモトくんの望む結果に改竄かいざんすることができます。

 ```

0 1 2
| | |
+-+ |
| +-+
| | |
1 2 0
```
Sample Explanation 2
### 出力例2

 ```
2
```

サワくんが作成したあみだくじは下記のようになります。

 ```

0 1 2 3
| | | |
+-+ | |
| | +-+
+-+ | |
| | +-+
| | | |
0 1 2 3
```

$ 2 $ 本の横線を書き足すことでオカモトくんの望む結果に改竄かいざんすることができます。

 ```

0 1 2 3
| | | |
+-+ | |
| | +-+
| +-+ |
+-+ | |
| | +-+
| +-+ |
| | | |
3 2 1 0
```
```