問題文

$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$

出力

答えを出力せよ。

入力例 1

2 4
1 1
1 2
2 0
4 2

出力例 1

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$ を出力します。

入力例 2

1 1
1 1

出力例 2

0

白のポーンを $(0,1)$ から動かすことはできません。