Problem

Consider a square grid of size ~N~. There are ~M~ distinct directed light sources placed at the vertices of the grid. In the diagram below, the light sources are marked in dark color.

Flat mirrors of one face can be placed at the vertices of the grid not occupied by light sources, at a ~45~-degree angle with respect to the sides of the grid. These mirrors change the direction of the emitted light by ~90~ degrees. A possible arrangement of mirrors and a path that the light can follow inside the grid, if the sources are properly oriented, is shown in the diagram below.

Light beams cannot pass through mirrors or light sources, and they cannot intersect.

Task

Write a program that calculates the maximum number of light beams that can exit the grid.

Input Data

The program reads the data from the file escape.in. The first line of the file contains two numbers, ~N~ and ~M~. The next ~M~ lines contain the coordinates ~X_i~ and ~Y_i~ of a light source. For each ~1 \le i \le M~, it holds ~1 \le X_i \le N~ and ~1 \le Y_i \le N~.

Example of Input:

6 10
1 3
2 2
2 3
2 4
4 2
4 3
4 4
6 2
6 3
6 4

This corresponds to the above grid.

Output Data

The result should be a text file named escape.out. It should contain only one line with the requested maximum number of light beams.

Example of Output:

10

The same output should result if we add another light source at coordinates ~5~ ~3~ to the above grid.

Constraints

~1 \le N \le 100~
~1 \le M \le 1000~
Your program will run for at most ~5~ sec.