Description

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.

Input Format

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 Format

Output the maximum number of knights that can coexist.

3 2
1 1
3 3

5

Hint

Constraints

For all test points, it is guaranteed that $1 \leq n \leq 200$, $0 \leq m \lt n^2$.

Translated by ChatGPT 5