给定一个 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 个位置的棋子:
例如,方格 ( 4,4 ) 的棋子马 能攻击以下位置的格子,如图所示:
现在你想放一个棋子马到棋盘的空格中,但不能被其他马攻击。请问:棋盘上有多少个格子可以放置你的棋子?
第一行, N 和 M
接下来 M 行,其中第 i 行表示第 i 个马的位置 ( a_i, b_i ), 1≤i≤M
输出能放置马的空格子数目(但不能被其他马攻击)
8 6 1 4 2 1 3 8 4 5 5 2 8 3
38
解释:有38个空格子(蓝底色)可以放置你的马。
1000000000 1 1 1
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)
所有输入数据均为整数。