C - 天下一不正 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

サワくんは天下一プログラマーコンテスト 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行で出力せよ。出力の末尾には改行を入れること。

配点

この問題には部分点が設定されている。

  • H \leq{} 100 を満たすテストケース全てに正解した場合は、45 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 105 点が与えられる。

入力例1

3 1
0
1 2 0

出力例1

1

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

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

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

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

入力例2

4 4
0 2 0 2
3 2 1 0

出力例2

2

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

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

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

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