白色棋子

题目描述

设 $N$ 为正整数。 有一个 $(2N+1) \times (2N+1)$ 的网格,行编号为 $0$ 到 $2N$,列编号也为 $0$ 到 $2N$。用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。

我们有一个白色棋子,初始位于 $(0, N)$。 此外,有 $M$ 个黑色棋子,第 $i$ 个位于 $(X_i, Y_i)$。

当白色棋子位于 $(i, j)$ 时,可以执行以下操作之一来移动它:

• 如果 $0 \le i \le 2N-1$, $0 \le j \le 2N$,且 $(i+1,j)$ 上没有黑色棋子,把白色棋子移到 $(i+1, j)$。
• 如果 $0 \le i \le 2N-1$, $0 \le j \le 2N-1$,且 $(i+1,j+1)$ 上有黑色棋子,把白色棋子移到 $(i+1, j+1)$。
• 如果 $0 \le i \le 2N-1$, $1 \le j \le 2N$,且 $(i+1,j-1)$ 上有黑色棋子,把白色棋子移到 $(i+1, j-1)$。

黑色棋子不能移动。

求满足「通过重复执行这些操作,可以把白色棋子移到 $(2N, Y)$」的整数 $Y$ 的个数。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

输出格式

输出答案。

样例

2 4
1 1
1 2
2 0
4 2

3

可以按如下方式把白色棋子移到 $(4,0)$, $(4,1)$, $(4,2)$:

$(0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)$

$(0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)$

$(0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)$

另一方面,无法把它移到 $(4,3)$ 或 $(4,4)$。因此,应输出 $3$。

1 1
1 1

0

无法把白色棋子从 $(0,1)$ 移走。

数据范围

• $1 \le N \le 10^9$
• $0 \le M \le 2 \times 10^5$
• $1 \le X_i \le 2N$
• $0 \le Y_i \le 2N$
• $(X_i, Y_i) \neq (X_j, Y_j)$($i \neq j$)
• 输入均为整数