AT_abc203_e [ABC203E] White Pawn

[problemUrl]: https://atcoder.jp/contests/abc203/tasks/abc203_e $ 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 $

答えを出力せよ。

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