#P0012. 避开老马

避开老马

问题陈述

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

每个方格要么是空的,要么放了一颗棋子。网格上有 MM 个棋子,而第 kk (1≤k≤M)(1\leq k\leq M) 个棋子被放在了 (ak,bk)(a_k,b_k) 格上。

您想把棋子放在空方格上,并且它不会被任何现有棋子吃掉。

放置在位置 (i,j)(i,j) 上的棋子可以吃掉满足以下任何条件的棋子:

  • 置于位置 (i+2,j+1)(i+2,j+1) 上
  • 置于位置 (i+1,j+2)(i+1,j+2) 上
  • 置于位置 (i−1,j+2)(i-1,j+2) 上
  • 置于位置 (i−2,j+1)(i-2,j+1) 上
  • 置于位置 (i−2,j−1)(i-2,j-1) 上
  • 置于位置 (i−1,j−2)(i-1,j-2) 上
  • 置于位置 (i+1,j−2)(i+1,j-2) 上
  • 置于位置 (i+2,j−1)(i+2,j-1) 上

当然,此外,我们也不可以吃掉棋盘以外的棋子。

例如,放在 (4,4)(4,4) 位置上的棋子可以吃掉下图中蓝色所示位置上的棋子:

还是那个问题,您可以将棋子放在几个位置上?

输入

输入内容由标准输入法提供,格式如下

NN MM
a1a_1 b1b_1
a2a_2 b2b_2
⋮\vdots
aMa_M bMb_M

此外,保证输入数据满足以下条件:

  • 1≤N≤1091\leq N\leq10^9
  • 1≤M≤2×1051\leq M\leq2\times10^5
  • 1≤ak≤N,1≤bk≤N (1≤k≤M)1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
  • (ak,bk)≠(al,bl) (1≤k<l≤M)(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq 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

提示

样例 11 解释

现有棋子可以吃掉下图中蓝色方格中的棋子: 图片

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