题目描述

噜噜正在给自己的“噜噜飞艇”装载补给箱。

飞艇货舱被划分为 $n$ 条平行通道（记为第 $1\sim n$ 条通道），每条通道上有 $10$ 个固定卡槽（位置编号为 $1\sim 10$）。其中第 $3$ 与第 $4$ 卡槽之间、以及第 $7$ 与第 $8$ 卡槽之间有隔断（也就是说，$(r,3)$ 与 $(r,4)$ 不视为相邻，$(r,7)$ 与 $(r,8)$ 也不视为相邻）。

布局如图所示：

噜噜要尽可能多地装入 一组“四联补给箱”。每组补给箱共有 4 个小箱子，要求放在同一条通道内：

• 常规装载：占据 连续 的 4 个卡槽；

• 特殊装载：允许跨过隔断，把 4 个小箱子拆成隔断两侧 各 2 个（例如同一通道放在 $2,3$ 与 $4,5$ 位置，这种“隔断两边各两个”的装载方式允许）。

现在有 $m$ 个卡槽已经损坏或被占用（不可用）。请你计算：噜噜最多能装入多少组“四联补给箱”。

输入格式

第一行包含两个整数 $n,m$，分别表示通道数以及不可用卡槽数量。

接下来 $m$ 行，每行两个整数 $r_i,c_i$，表示第 $r_i$ 条通道的第 $c_i$ 个卡槽不可用。

输出格式

输出一个整数，表示最多能装入的“四联补给箱”组数。

3 6
1 2
1 3
1 8
2 6
3 1
3 10

4

样例解释 1

存在一种最优装载方案，总共能装入 4 组：第 1 条通道装入 1 组，第 2 条通道装入 1 组，第 3 条通道装入 2 组，总计 $1+1+2=4$。

2 3
2 1
1 8
2 6

2

数据范围

• $1 \le n \le 10^9$
• $1 \le m \le \min(10 \times n,\ 2\times 10^5)$
• $1 \le r_i \le n$
• $1 \le c_i \le 10$
• 保证所有不可用卡槽坐标互不相同。

子任务与特殊性质

性质 A： 所有不可用卡槽的列号 $c_i$ 仅可能为 $1$ 或 $10$。
性质 B： 对于所有出现不可用卡槽的通道，该通道 恰好只有一个 卡槽不可用。