P3355 Knights Coexistence Problem

On an $n \times n$ chessboard, a knight can attack the squares shown in the figure. Some squares on the board are marked as obstacles, and knights are not allowed to enter them.  Given an $n \times n$ chessboard and the obstacle marks, compute the maximum number of knights that can be placed on the board so that no two knights attack each other.

The first line contains $2$ positive integers $n$ and $m$, representing the size of the board and the number of obstacles, respectively. The following $m$ lines give the positions of the obstacles. Each line contains $2$ positive integers, representing the coordinates of an obstructed square.

Output the maximum number of knights that can coexist.

#### Constraints For all test points, it is guaranteed that $1 \leq n \leq 200$, $0 \leq m \lt n^2$. Translated by ChatGPT 5