思路

• 关键性质：对任意人位置 $(x,y)$，对角线上出口 $(i,i)$ 的距离为 $|x-i|+|y-i|$。当 $i\in[\min(x,y),\max(x,y)]$ 时，有

且这是最小值。因此该人可选择的最近出口集合恰为整数区间

题目内容

给定一个大小为几 $n×n$ 的迷宫，迷宫的单元格以坐标 $(x,y)$ 表示，其中 $1≦x,y≦n$ 。

在迷宫中有 $m$ 个人，每个人初始位于坐标 $(x_i,y_i)$ 。他们每一步可以移动到一个与当前位置四相邻的单元格。

在坐标 $(i,i)(1≦i≦n)$ 的位置上有 $n$ 个出口。每个出口只能使用一次，当有人在该出口逃出迷宫后，该出口即刻关闭。

每个人会选择离自己最近的出口(最小曼哈顿距离)作为逃生终点。若存在多个最近的出口，人员之间会协调分配，以使最终逃出的人数最大化。

当所有人按照上述规则前往各自目标出口后，计算最终有多少人能够成功逃出迷宫。

【名词解释】

• 四相邻：四相邻 是指当 $|x-x'|+|y-y'|=1$ 时，单元格 $(x,y)$ 与 $(x',y')$ 被认为相邻的，可以在一步中相互移动。

• 曼哈顿距离：两个点 $(x_1,y_1),(x_2,y_2)$ 之间的曼哈顿距离为他们横坐标加纵坐标差，即 $|x_1-x_2|+|y_1-y_2|$

输入描述

第一行输入两个整数 $n$ 和 $m(2≦n,m≦10^6)$ ，分别表示迷宫的边长与人的数量。

接下来 $m$ 行，每行输入两个整数 $x_i$ 和 $y_i$ $(1≦x_i,y_i≦n)$ ，表示第 $i$ 个人的初始坐标。

输出描述

输出一个整数，表示最终能够逃出迷宫的人的数量。

样例1

输入

2 3
1 2
2 1
1 1

输出

2

说明

在这个样例中：

• 迷宫有 $2$ 个出口，分别位于 $(1,1)$ 和 $(2,2)$；

• $3$ 位人分别位于 $(1,2),(2,1),(1,1)$ ；

• 每个出口只能使用一次，所以最多有 $2$ 个出口被使用，因此共有 $2$ 人逃出。

样例2

输入

4 3
1 2
1 2
1 2

输出

2

说明

在这个样例中：

• 迷宫有 $4$ 个出口，分别位于 $(1,1),(2,2),(3,3),(4,4)$ ；

• $3$ 位人分别位于 $(1,2)$ ，距离出口的距离为 $1,1,3,5$

• 他们三人都只会选择 $(1,1),(2,2)$ 的出口，因出口有人进入后会关闭所以三人中只有两个人能逃出。

• 出口 $(3,3)$ 和 $(4,4)$ 未被使用，因为它们并非任何人的最近出口(距离为 $3,5$ ) 。