AT_abc436_c.[ABC436C] 2x2 Placing

有一个 $N$ 行 $N$ 列的网格。令 $(i,j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。最初，网格上没有放置任何物品。

你将进行 $M$ 次操作。第 $i$ 次操作（$1\leq i\leq M$）如下：

• 如果以单元格 $(R_i,C_i)$ 为左上角的 $2\times 2$ 区域上没有任何已放置的方块，就在该区域放置一个方块。更具体地说，对于 $S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace$，如果这四个格子中有任意一个已经被其他方块占用，则不进行任何操作；否则，在 $S$ 所有四个格子上放置一个方块。

请在所有操作结束后，求最终共放置了多少个方块。

输入从标准输入读入，格式如下：

$N$ $M$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_M$ $C_M$

输出答案。

样例解释 1

下图展示了操作过程，黑色区域表示已放置的方块，红色方框表示下一步将要尝试放置方块的位置。

• 操作 1：选中以 $(1,1)$ 为左上角的 $2\times 2$ 区域，没有格子被占用，因此放置方块。
• 操作 2：以 $(2,2)$ 为左上角的 $2\times 2$ 区域中，$(2,2)$ 这个格子已被方块占用，所以不放置。
• 操作 3：以 $(2,3)$ 为左上角的 $2\times 2$ 区域中没有格子被占用，因此放置方块。

因此，所有操作结束后共放置了 $2$ 个方块。

样例解释 2

每次操作都可以成功放置一个方块。

样例解释 3

可能存在 $i,j\ (i\neq j)$ 使得 $(R_i,C_i)=(R_j,C_j)$。

数据范围

• $2\leq N \leq 10^9$
• $1\leq M \leq 2\times 10^5$
• $1\leq R_i,C_i \leq N-1$
• 所有输入值均为整数。

由 ChatGPT 5 翻译