Problem Description

Given an $N$ by $N$ chessboard, it is known that some cells are forbidden to place on.

Find the maximum number of dominoes of length $2$ and width $1$ that can be placed on the board. The boundary of each domino must align with the grid lines (each domino occupies two cells), and no two dominoes may overlap.

Input Format

The first line contains two integers $N$ and $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$ and column $y$ is forbidden. Row and column indices start from $1$.

Output Format

Output one integer, the result.

8 0

32

Hint

$1 \le N \le 100$，$0 \le t \le 100$

Translated by ChatGPT 5