← 返回题目列表

Codeforces · 333/B

B. 芯片

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

杰拉德玩以下游戏。他有一个大小为 n × n 个格子的格子场,其中 m 个不同的格子被禁止。在比赛之前,他必须在一些边界(但不是角落)棋盘单元上放置一些筹码。然后,在 n - 1 分钟内,Gerald 每分钟将每个芯片移动到相邻的单元格中。他将每个筹码从其原始边缘移动到相反的边缘。杰拉德在这场比赛中在以下三种情况下都输了:

- 至少有一个筹码至少曾经落入禁区。
- 至少有一次两个芯片位于同一单元上。
- 一分钟内至少交换两个筹码(例如,如果将两个筹码放置在长度相等的行的两个相对的边界单元上,则这种情况发生在该行的中间)。

在这种情况下,他输了并获得 0 分。当没有发生类似的情况时,他获胜并获得的分数等于他在棋盘上投入的筹码数量。帮助杰拉德获得最多积分。

输入

第一行包含两个空格分隔的整数 n 和 m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 105) — 字段的大小和禁止单元格的数量。接下来的 m 行每行包含两个空格分隔的整数。具体来说,这些行中的第 i 行包含数字 xi 和 yi (1 ≤ xi, yi ≤ n) — 第 i 个禁止单元格的坐标。所有给定的单元格都是不同的。

考虑字段行从上到下从 1 到 n 编号,列从左到右从 1 到 n。

输出

打印一个整数——杰拉德在这场游戏中可以获得的最高分。

示例

输入 #1

3 1
2 2

输出 #1

0

输入 #2

3 0

输出 #2

1

输入 #3

4 3
3 1
3 2
3 3

输出 #3

1

注意

在第一个测试中,答案等于零,因为我们无法将芯片放入角单元中。

在第二个示例中,我们可以将一个芯片放入单元 (1, 2)、单元 (3, 2)、单元 (2, 1) 或单元 (2, 3) 中。我们不能放置两个芯片。

在第三个示例中,我们只能将一个芯片放入单元格 (2, 1) 或单元格 (2, 4) 中。