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 翻译