Knight

The knight is a chess piece that can move from the square marked S to any of the eight squares marked X in the figure below. If another piece occupies the destination square, the knight captures it.

You are given an N×N chessboard. You want to place knights so that no two knights can capture each other in a single move. Write a program that finds the maximum number of knights that can be placed. However, knights cannot be placed on M given squares.

The first line contains two integers N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ N²), separated by a space. Each of the next M lines contains the position of one square where a knight cannot be placed. Each position is given as two integers, where the top-left square of the board is (1, 1) and the bottom-right square is (N, N).

Print the maximum number of knights that can be placed so that no two of them can capture each other.