Problem Description

Given an $N \times M$ chessboard, some cells are forbidden for placing pieces.

Find the maximum number of knights (the “knight” in international chess, similar to the “horse” in Chinese chess, which attacks in an L-shape, but without the “blocked leg” rule in Chinese chess) that can be placed on the board so that no two knights attack each other.

Input Format

The first line contains three integers $N, M, T$, where $T$ is the number of forbidden cells.

The next $T$ lines each contain two integers $x$ and $y$, indicating that the cell at row $x$, column $y$ is forbidden for placement. Rows and columns are numbered starting from $1$.

Output Format

Output one integer representing the result.

2 3 0

4

Hint

$1 \le N, M \le 100$

Translated by ChatGPT 5