该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

八路军根据地可以看成一个行号和列号都是从 0 到 $2N（N\le10^9）$ 的方阵。区域中有些格子修筑有鬼子炮楼。

游击队一开始位于第 0 行第 $N$ 列向正南东南和西南三个方向攻击前进。幸运的是，鬼子们都出去扫荡了，现在炮楼都由二狗子把手，二狗子比较傻，只会往正北方向警戒。

当游击队位于 $(i,j)$ 时，可以通过以下任一操作前进：

• 若 $0\leq i\leq 2N-1$，$0\leq j\leq 2N$，且 $(i+1,j)$ 没有炮楼，则可以移动到 $(i+1,j)$。
• 若 $0\leq i\leq 2N-1$，$0\leq j\leq 2N-1$，且 $(i+1,j+1)$ 有炮楼，则可以端掉炮楼然后移动到 $(i+1,j+1)$。
• 若 $0\leq i\leq 2N-1$，$1\leq j\leq 2N$，且 $(i+1,j-1)$ 有炮楼，则可以端掉炮楼然后移动到 $(i+1,j-1)$。

问游击队到达最南面一行时，最终可以到达的不同格子数量。

Format

Input

第一行两个正整数 $N$ 和 $M$，分别表示根据地大小和炮楼数量。

后面 $M$ 行，每行给出一个炮楼坐标。

Output

最下面一行中，游击队可以到达的格子数量。

Samples

3 1
1 2

2

Limitation

1s, 1024KiB for each test case.