P5182 Board Tiling

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.

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 one integer, the result.

$1 \le N \le 100$，$0 \le t \le 100$ Translated by ChatGPT 5