Problem Description

One day, while Taro was taking a walk, a suspicious machine fell from the sky. Taro, intrigued by the machine, decided to pick it up and examine it.

It seems that this machine has lights arranged in a grid of $H$ rows and $W$ columns, each of which can be in one of two states: ON or OFF. Pressing a light will toggle its state and the states of the lights adjacent to it (up, down, left, and right).

However, some of the lights were broken due to the impact of the fall and cannot be pressed. However, pressing adjacent lights will still toggle the state of the broken lights as usual.

Taro is curious about the minimum number of light presses needed to turn all the lights OFF. Help Taro by finding the minimum number of light presses required to turn all the lights OFF.

Input Format

The input is given from the standard input in the following format:

$ 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 $

• The first line contains $ H, W $ ($5 \leq H, W$, $H \times W \leq 400$), representing the number of rows and columns of the lights on the machine.
• The next $ H $ lines contain $ W $ numbers each, separated by spaces, where $ 0 $ represents a light in the OFF state and $ 1 $ represents a light in the ON state.
• The $ H+1 $th line contains the number of broken lights $ N $ ($0 \leq N \leq W \times H$).
• The next $ N $ lines contain the coordinates of the broken lights, where $ x_i $ ($0 \leq x_i \leq W-1$) is the column and $ y_i $ ($0 \leq y_i \leq H-1$) is the row.
• It is guaranteed that there is a way to turn off all the lights.
• The same coordinates will not be given twice, meaning that if $i \neq j$, then $x_i \neq x_j$ or $y_i \neq y_j$.

Output Format

Output the minimum number of presses required to turn all the lights OFF in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 5
0 0 0 0 0
1 1 0 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 0 0
0

Sample Output #1

5

Sample Input #2

5 5
0 0 0 0 0
1 1 0 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 0 0
1
1 2

Sample Output #2

9

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分