配点 : $500$ 点

問題文

$N$ を正の整数とします。 行と列にそれぞれ $0$ から $2N$ までの番号が付いた $(2N+1)\times (2N+1)$ のマス目があり、行 $i$ かつ列 $j$ に属するマスを $(i,j)$ で表します。

白のポーンが $1$ つあり、最初 $(0,N)$ に置かれています。 黒のポーンは $M$ 個あり、$i$ 個目の黒のポーンは $(X_i, Y_i)$ に置かれています。

白のポーンが $(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)$ に動かす。

黒のポーンは動かすことができません。

この操作を繰り返した結果、$(2N,Y)$ に白のポーンが置かれている状態にできるような $Y$ の値としてあり得るものの個数を求めてください。

制約

• $1 \leq N \leq 10^9$
• $0 \leq M \leq 2\times 10^5$
• $1 \leq X_i \leq 2N$
• $0 \leq Y_i \leq 2N$
• $(X_i, Y_i) \neq (X_j, Y_j)$ $(i \neq j)$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$X_1$ $Y_1$

$:$

$X_M$ $Y_M$

出力

答えを出力せよ。

2 4
1 1
1 2
2 0
4 2

3

$(4,0)$, $(4,1)$, $(4,2)$ の $3$ つへはそれぞれ次のように動かせます:

• $(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)$ から動かすことはできません。