分数: 300 点
问题陈述
有一个网格 N^2 方块与 N 行和 N 列。 让 (i,j) 表示 i从顶部算起的第行 (1\leq i\leq N) 和 j左起第 列 (1\leq j\leq N).
每个方格要么是空的,要么上面放置了一个棋子。 有 M 棋子放置在网格上,并且 k-th (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) 可以吃下图蓝色方块上的棋子:

你可以把你的棋子放在多少个方格上?
约束
- 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 \vdots a_M b_M
输出
打印出可以放置棋子而不会被任何现有棋子捕获的空方格的数量。
示例输入 1
8 6 1 4 2 1 3 8 4 5 5 2 8 3
示例输出 1
38
现有棋子可以吃掉下图蓝色格子上的棋子:

因此,您可以将您的棋子放在剩余的棋子上 38 方块。
示例输入 2
1000000000 1 1 1
示例输出 2
999999999999999997
超出 10^{18} 正方形,仅限 3 不能使用方块:方块 (1,1), (2,3),和 (3,2).
请注意,答案可能是 2^{32} 或更大。
示例输入 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