该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个由 $N^2$ 个正方形组成的网格，网格中有 $N$ 行和 $N$ 列。让 $(i,j)$ 表示从上往下 $(1\leq i\leq N)$ 的第 $i$ 行和从左往上 $(1\leq j\leq N)$ 的第 $j$ 列的正方形。

每个方格要么是空的，要么放了一颗棋子。网格上有 $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)$ 位置上的棋子可以吃掉下图中蓝色所示位置上的棋子：

您可以将棋子放在几个位置上？

输入格式

输入包含两个整数 $N$ 和 $M$，接着 $M$ 行，每行包含两个整数 $a_k$ 和 $b_k$，表示第 $k$ 个棋子的位置。

输出格式

输出一个整数，表示可以放置棋子且不会被任何已放置棋子吃掉的空方格数量。

样例

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

38

1000000000 1
1 1

999999999999999997

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

338

提示

• $1 \leq N \leq 10^9$
• $1 \leq M \leq 2 \times 10^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 < l \leq M)$
• 所有输入值均为整数

样例解释 1

已放置的棋子可以吃掉下图中蓝色表示的格子上的棋子。因此，你可以将棋子放在剩下的 $38$ 个格子上。

样例解释 2

在 $10^{18}$ 格中，只有 $(1,1)$、$(2,3)$ 和 $(3,2)$ 这 $3$ 个格子不能放置棋子。最终结果为 $2^{32}$ 以上的一个值。