Background

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

Problem Description

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.

Input Format

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 Format

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

2 2 1
1 1

3

8 7 5
1 1
5 4
2 3
4 7
8 3

28

Hint

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