分数: 500 点
问题陈述
让 N 是正整数。 我们有一个 (2N+1)\times (2N+1) 行编号的网格 0 通过 2N 和列也已编号 0 通过 2N。让 (i,j) 表示 Row 处的方块 i 和专栏 j.
我们有一个白色棋子,最初位于 (0, N)。 另外,我们还有 M 黑色棋子, i- 第一个位于 (X_i, Y_i).
当白棋位于 (i, j),您可以执行以下操作之一来移动它:
- If 0\leq i\leq 2N-1, 0 \leq j\leq 2N 按住并 (i+1,j) 不 包含一个黑色棋子,将白色棋子移动到 (i+1, j).
- If 0\leq i\leq 2N-1, 0 \leq j\leq 2N-1 按住并 (i+1,j+1) 确实 包含一个黑色棋子,将白色棋子移动到 (i+1,j+1).
- If 0\leq i\leq 2N-1, 1 \leq j\leq 2N 按住并 (i+1,j-1) 确实 包含一个黑色棋子,将白色棋子移动到 (i+1,j-1).
你不能移动黑色棋子。
查找整数的个数 Y 使得白棋可以在 (2N, 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),如下:
- (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) or (4,4)。 因此,我们应该打印 3.
示例输入 2
1 1 1 1
示例输出 2
0
我们无法将白色棋子从 (0,1).