Score : $300$ points

问题陈述

有一个由 $N^2$ 个方格组成的网格，其中包含 $N$ 行和 $N$ 列。用 $(i,j)$ 表示从顶部数第 $i$ 行（$1\leq i\leq N$）和从左边数第 $j$ 列（$1\leq j\leq N$）的方格。

每个方格要么是空的，要么上面放置了一个棋子。网格上放置了 $M$ 个棋子，第 $k$ 个（$1\leq k\leq M$）棋子放置在方格 $(a_k,b_k)$ 上。

你想要在一个空方格上放置你的棋子，使得它不能被任何现有的棋子捕获。

放置在方格 $(i,j)$ 上的棋子可以捕获满足以下任一条件的棋子：

• 放置在方格 $(i+2,j+1)$
• 放置在方格 $(i+1,j+2)$
• 放置在方格 $(i-1,j+2)$
• 放置在方格 $(i-2,j+1)$
• 放置在方格 $(i-2,j-1)$
• 放置在方格 $(i-1,j-2)$
• 放置在方格 $(i+1,j-2)$
• 放置在方格 $(i+2,j-1)$

在这里，涉及不存在的方格的条件被认为是永远不会满足的。

例如，放置在方格 $(4,4)$ 上的棋子可以捕获下图中蓝色方格上的棋子：

你可以在多少个方格上放置你的棋子？

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a grid of $N^2$ squares with $N$ rows and $N$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top $(1\leq i\leq N)$ and $j$-th column from the left $(1\leq j\leq N)$.

Each square is either empty or has a piece placed on it. There are $M$ pieces placed on the grid, and the $k$-th $(1\leq k\leq M)$ piece is placed on square $(a_k,b_k)$.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square $(i,j)$ can capture pieces that satisfy any of the following conditions:

• Placed on square $(i+2,j+1)$
• Placed on square $(i+1,j+2)$
• Placed on square $(i-1,j+2)$
• Placed on square $(i-2,j+1)$
• Placed on square $(i-2,j-1)$
• Placed on square $(i-1,j-2)$
• Placed on square $(i+1,j-2)$
• Placed on square $(i+2,j-1)$

Here, conditions involving non-existent squares are considered to never be satisfied.

For example, a piece placed on square $(4,4)$ can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• $1\leq N\leq10^9$
• $1\leq M\leq2\times10^5$
• $1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)$
• $(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

$a_M$ $b_M$

Output

Print the number of empty squares where you can place your piece without it being captured by any existing pieces.

Sample Input 1

8 6
1 4
2 1
3 8
4 5
5 2
8 3

Sample Output 1

38

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining $38$ squares.

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999999999999997

Out of $10^{18}$ squares, only $3$ squares cannot be used: squares $(1,1)$, $(2,3)$, and $(3,2)$.

Note that the answer may be $2^{32}$ or greater.

Sample Input 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

Sample Output 3

338