题目描述
设 N 是一个正整数。我们有一个 (2N+1)times(2N+1) 的网格，其中行的编号从 0 到 2N，列也从 0 到 2N 编号。(i,j) 表示位于第 i 行、第 j 列的方格。
我们有一个白色的棋子，最初位于 (0,N)。此外，我们有 M 个黑色的棋子，第 i 个棋子位于 (Xi,Yi)。
当白色棋子位于 (i,j) 时，你可以进行以下操作之一来移动它：
- 如果满足 0leqileq2N−1，0leqjleq2N 且 (i+1,j) 不包含一个黑色棋子，则将白色棋子移动到 (i+1,j)。
- 如果满足 0leqileq2N−1，0leqjleq2N−1 且 (i+1,j+1) 包含一个黑色棋子，则将白色棋子移动到 (i+1,j+1)。
- 如果满足 0leqileq2N−1，1leqjleq2N 且 (i+1,j−1) 包含一个黑色棋子，则将白色棋子移动到 (i+1,j−1)。
你不能移动黑色棋子。
找出整数 Y 的数量，满足通过重复这些操作，白色棋子可以位于 (2N,Y)。
约束条件
- 1leqNleq109
- 0leqMleq2times105
- 1leqXileq2N
- 0leqYileq2N
- (Xi,Yi)neq(Xj,Yj) （ineqj）
- 输入的所有值均为整数。
输入
输入以以下格式从标准输入给出：
N M
X1 Y1
:
XM YM
输出
输出答案。
示例输入1
2 4
1 1
1 2
2 0
4 2
示例输出1
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。
示例输入2
1 1
1 1
示例输出2
0
我们不能将白色棋子从 (0,1) 移动。
