AT_oidashi_b.ライツアウト

有一天，太郎在散步时，天上掉下来了一台奇怪的机器。太郎对这台机器产生了兴趣，于是捡起来研究了一下。

这台机器上排列着 $H$ 行 $W$ 列的灯，每个灯有“开（ON）”和“关（OFF）”两种状态。如果按下某个灯，这个灯以及与其上下左右相邻的灯的状态都会反转。

（按下中央红圈的灯时的示意图）

但是，由于掉落时的冲击，有些灯坏掉了，无法被按下。不过，按下相邻的灯时，坏掉的灯的状态仍会像正常一样被反转。

太郎想知道，要将所有灯的状态都变为“关（OFF）”，最少需要按多少次灯。请你帮太郎求出将所有灯的状态都变为“关（OFF）”所需的最小按灯次数。

输入通过标准输入给出，格式如下：

$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$）表示机器上灯的行数和列数。
• 接下来的 $H$ 行，每行有 $W$ 个用空格分隔的数字 $0$ 或 $1$，$0$ 表示该灯为“关（OFF）”，$1$ 表示该灯为“开（ON）”。
• 第 $H+1$ 行，$N$（$0 \leq N \leq W \times H$）表示坏掉的灯的数量。
• 接下来的 $N$ 行，每行两个整数 $x_i$（$0 \leq x_i \leq W-1$）、$y_i$（$0 \leq y_i \leq H-1$），表示坏掉的灯的列和行坐标。
• 保证一定存在一种操作方法可以将所有灯全部关掉。
• 坏掉的灯的坐标不会重复。

输出一个整数，表示将所有灯的状态变为“关（OFF）”所需的最小按灯次数。输出后请换行。

由 ChatGPT 4.1 翻译