B - ライツアウト

Contest Duration: 2016-02-28 16:01:12+0900 - 2016-02-28 19:00:00+0900 (local time) (178 minutes)

B - ライツアウト Editorial

Time Limit: 4 sec / Memory Limit: 291 MB

ある日、太郎くんが散歩をしていると、空から怪しい機械が落ちてきました。その機械が気になった太郎くんは拾って調べてみることにしました。

どうやらこの機械には縦Hマス、横Wマスの形に並んだON、OFFの2通りの状態を取るライトがあり、あるライトを押すとそのライトとそのライトに隣接する上下左右のライトのON、OFFが反転するようです。

しかし、落下時の衝撃でいくつかのライトが壊れてしまい押すことができなくなってしまっています。ただし、隣接するライトを押すと壊れたライトの状態は通常通り反転するようです。

太郎くんは、全てのライトの状態をOFFにするのに必要な最小のライトを押す回数が気になりました。太郎くんのために全てのライトの状態をOFFにするために必要な最小のライトを押す回数を求めてください。

入力は以下の形式で標準入力から与えられます。(標準入力中の変数を修正しました。(18:38))

H W
s_{0,0} s_{0,1} ... s_{0,(W-1)}
s_{1,0} s_{1,1} ... s_{1,(W-1)}
.
.
.
s_{(H-1),0} s_{(H-1),1} ... s_{(H-1),(W-1)}
N
x_1 y_1
x_2 y_2
.
.
.
x_n y_n

1行目の、H, W (5 \leq H,W， H \times W \leq 400)は機械についているライトの行数と列数を表します。
2行目以降のH行には、空白区切りでW個の0か1の数字が与えられます。0はライトの状態がOFF、1はライトの状態がONを表します。
H+1行目には壊れているライトの数N(0 \leq N \leq W \times H)が与えられます。(16:21 追記)
H+2行目以降のN行には、壊れているライトの列x_i(0 \leq x_i \leq W-1), 行y_i (0 \leq y_i \leq H-1)が与えられます。
この問題ではすべてのライトを消す手順があることが保証されています。(16:15 追記)
同じ座標は二度与えられません。つまり、i \neq j ならば x_i \neq x_j または y_i \neq y_j が成り立ちます。(18:08 追記)

全てのライトの状態をOFFにするための最小の反転回数を1行で出力してください。出力の末尾には改行を入れること。