C. 避免马攻击

内存限制:256 MiB 时间限制:1000 ms 输入文件: knight.in 输出文件: knight.out
题目类型:传统 评测方式:文本比较

题目描述

给定一个 N*N 的网格棋盘。( 1,1 ) 是网格左上角的格子,( i,j ) 表示第 i 行第 j 列的格子。( 1≤i≤N,1≤j≤N )

每个格子或者是空,或者放置一个棋子马。现有 M 个马在棋盘上,其中第 k 个马的位置是 ( a_k​ ,b_k​ ) ( 1≤k≤M ).

在格子 ( i,j ) 中的棋子马能 攻击以下 8 个位置的棋子:

  • 格子 ( 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 行,其中第 i 行表示第 i 个马的位置 ( a_i​, b_i ), 1≤i≤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

解释:只有3个方格不能用, (1,1), (2,3), (3,2)。

数据范围与提示

1≤N≤10^9

1≤M≤2×10^5

1≤a_k ≤N,1≤b_k ≤N (1≤k≤M)

(a_k​ ,b_k) \neq (a_l​ ,b_l​ ) (1≤k<l≤M)

所有输入数据均为整数。