问题陈述
有一个由 N2 个正方形组成的网格,网格中有 N 行和 N 列。让 (i,j) 表示从上往下 (1≤i≤N) 的第 i 行和从左往上 (1≤j≤N) 的第 j 列的正方形。
每个方格要么是空的,要么放了一颗棋子。网格上有 M 个棋子,而第 k (1≤k≤M) 个棋子被放在了 (ak,bk) 格上。
您想把棋子放在空方格上,并且它不会被任何现有棋子吃掉。
放置在位置 (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
a1 b1
a2 b2
⋮
aM bM
此外,保证输入数据满足以下条件:
- 1≤N≤109
- 1≤M≤2×105
- 1≤ak≤N,1≤bk≤N (1≤k≤M)
- (ak,bk)=(al,bl) (1≤k<l≤M)
- 所有输入值均为整数。
输出
输出在不被现有棋子吃掉的情况下可以放置棋子的空方格数。
样例 #1
样例输入 #1
8 6
1 4
2 1
3 8
4 5
5 2
8 3
样例输出 #1
38
样例 #2
样例输入 #2
1000000000 1
1 1
样例输出 #2
999999999999999997
样例 #3
样例输入 #3
20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15
样例输出 #3
338
提示
样例 1 解释
现有棋子可以吃掉下图中蓝色方格中的棋子:

因此您可以将棋子放在余下的 38 个位置上。