← 返回题目列表

AtCoder · abc203_e

E. 白色棋子

中文机器翻译题面 查看原题

分数: 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).