← 返回题目列表

AtCoder · abc377_c

E. 避免骑士攻击

中文机器翻译题面 查看原题

分数: 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