问题描述

有一个 $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$。

接下来 $M$ 行，每行输入两个正整数，表示 $(R_i,C_i)$。

输出格式

输出一个数字，表示答案。

样例输入1

4 3
1 1
2 2
2 3

样例输出1

2

样例输入2

8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1

样例输出2

8

说明

对于样例 $1$：

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

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

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

评测数据规模

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