Problem Description

You are given an $N\ ×\ N$ grid. Let $(i,\ j)$ denote the cell in the $ i $ -th row from the top ( $1\ \leq\ i\ \leq\ N$ ) and the $ j $ -th column from the left ( $1\ \leq\ j\ \leq\ N$ ).

Each cell is painted red if $ i+j $ is even, and blue if $ i+j $ is odd.

Next, for $ K $ cells, if a cell is painted red, it is repainted blue, and if it is painted blue, it is repainted red.

After that, you will choose some cells. The chosen cells must form a single contiguous rectangle without any holes.

You want the absolute difference between the number of red cells and the number of blue cells among the chosen cells to be as large as possible. What is the maximum possible value?

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ Y_1 $ $ X_1 $ $ Y_2 $ $ X_2 $ : $ Y_K $ $ X_K $

• The first line contains integers $N(1\ \leq\ N\ \leq\ 2000)$ and $K(1\ \leq\ K\ \leq\ 10)$ separated by a space.
• The following $ K $ lines contain information about the cells to be repainted. The $ i $ -th line contains integers $Y_i(1\ \leq\ Y_i\ \leq\ N)$ and $X_i(1\ \leq\ X_i\ \leq\ N)$ separated by a space, indicating that the color of cell $(Y_i,\ X_i)$ is to be repainted.
• If $i\ \neq\ j$ , then $Y_i\ \neq\ Y_j$ or $X_i\ \neq\ X_j$ is satisfied.

Output Format

Output the maximum absolute difference between the number of red cells and the number of blue cells. The output should be to the standard output, followed by a newline.

Sample Input and Output

Sample Input #1

3 1
1 1

Sample Output #1

2

Sample Input #2

3 4
1 2
2 1
2 3
3 2

Sample Output #2

9

Sample Input #3

3 4
1 1
1 3
3 1
3 3

Sample Output #3

7

Notes/Hints

Sample Explanation 1

In this case, choosing cells $(1,\ 1)$ and $(1,\ 2)$ yields the maximum answer, which is $ 2 $. Other combinations like $(1,\ 1)$ and $(2,\ 1)$ or $ (1,1),(1,2),(2,1),(2,2) $ also yield the answer $ 2 $.

Sample Explanation 2

In this case, all cells are painted red. Therefore, choosing all cells yields the maximum answer, which is $ 9 $.

Sample Explanation 3

In this case, all cells except the center one are painted blue. Therefore, choosing all cells yields the maximum answer, which is $ 7 $.

见题面 Input 部分

见题面 Output 部分