Bishop Placement 2

In chess, a bishop can move any distance along a diagonal and can capture a piece on that diagonal if the path is clear. In the figure below, the bishop on B can capture pieces on the cells marked O.

Some cells of the board may contain obstacles that bishops cannot pass through. If an obstacle lies on a diagonal path, a bishop cannot move or attack beyond that obstacle.

The size of a square chessboard is the number of cells on one side. Given the board size and the positions of all obstacles, find the maximum number of bishops that can be placed so that no two bishops can capture each other.

For the board shown in Figure 2, up to 10 bishops can be placed as shown in Figure 3.

The first line contains N, the size of the square chessboard. The second line contains M, the number of obstacles on the board.

N is a positive integer not greater than 100, and M is a nonnegative integer. Each of the next M lines contains the position of one obstacle. A position is given by two positive integers: the row counted from the top and the column counted from the left.

Print the maximum number of bishops that can be placed on the board.