P5030 Long-necked Giraffe Placement

As everyone knows, in chess, we have rooks, knights, queens, bishops, and long-necked giraffes.

As shown in the picture, the chess piece "long-necked giraffe" is similar to the knight in Chinese chess, but it attacks in a "目" shape, and there is no rule like the Chinese chess "blocking the horse's leg" (because the long-necked giraffe has no legs).  Given an $N \times M$ chessboard, some cells are forbidden to place pieces. Find the maximum number of long-necked giraffes that can be placed on the board such that none of them can attack each other.

The first line contains two positive integers $N, M, K$. Here, $K$ is the number of cells where placing a long-necked giraffe is forbidden. Lines $2$ to $K + 1$ each contain two integers $X_i, Y_i$, indicating a forbidden cell. It is not guaranteed that the forbidden cells are all distinct.

Output one positive integer in a single line, representing the maximum number of long-necked giraffes that can be placed.

For $10\%$ of the testdata, $1 \le N, M \le 5$. For $30\%$ of the testdata, $1 \le N, M \le 10$. For $60\%$ of the testdata, $1 \le N, M \le 50$. For $80\%$ of the testdata, $1 \le N, M \le 100$. For $100\%$ of the testdata, $1 \le N, M \le 200$. Translated by ChatGPT 5