题目描述

$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$ の値としてあり得るものの個数を求めてください。

输入格式

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

$N$ $M$ $X_1$ $Y_1$ $:$ $X_M$ $Y_M$

输出格式

答えを出力せよ。

题目大意

一个 $(2n+1)\times(2n+1)$ 的棋盘上有 $m$ 个黑棋，你有一个白棋在 $(0,n)$。当白棋在 $(i,j)$ 时，每次可以对白棋进行以下操作：

1. 如果 $(i+1,j)$ 没有黑棋，可以走到那。

2. 如果 $(i+1,j-1)$ 有黑棋，可以走到那。

3. 如果 $(i+1,j+1)$ 有黑棋，可以走到那。

不能走出棋盘。

问到 $2n+1$ 行时能到多少个点。

2 4
1 1
1 2
2 0
4 2

3

1 1
1 1

0

提示

制約

• $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)$
• 入力は全て整数である。

Sample Explanation 1

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

Sample Explanation 2

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