You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 最近在玩一款名叫“昨天原粥”的游戏。

这个游戏的地图可以看作是一个 $n$ 行 $m$ 列的二维数组。第 $i$ 行第 $j$ 列的位置用 $(i,j)$ 表示。

现在地图上有 $k$ 名干员，第 $i$ 名干员的位置在 $(x_i,y_i)$（保证不会有多名干员在同一个位置）。

你现在可以挑选一个 没有放干员 的位置施加魔法，所有与这个位置的曼哈顿距离不超过 $2$ 的干员都会被强化。

请你算算最多能强化多少干员。

什么是曼哈顿距离呢？
比如你在方格纸上走，只能横着走或者竖着走，不能斜着走。从一个格子到另一个格子，最少要走多少步，这就是它们的曼哈顿距离啦。
就像从 $(x,y)$ 到 $(a,b)$，先算横向差多少步（$x$ 和 $a$ 的差，不管正负，只算数字），再算纵向差多少步（$y$ 和 $b$ 的差，同样只算数字），把这两个数加起来，就是最少要走的步数啦。
在 C++ 中，abs(x) 可以得到 $x$ 的绝对值，即不管正负的数字部分。因此可以使用 abs(x-a)+abs(y-b) 来计算 $(x,y)$ 与 $(a,b)$ 之间的曼哈顿距离。

输入格式

第一行为三个整数 $n,m,k$。

接下来 $k$ 行，第 $i$ 行为第 $i$ 为干员的位置 $(x_i,y_i)$，保证每个位置只出现一次。

输出格式

一个整数，即最多能强化多少干员

4 5 3
1 1
4 2
2 5

2

样例 1 解释

三位干员的位置即下面的 o 的位置，显然在 # 的位置（$(2,2)$）施加魔法可以覆盖两位干员（$(1,1)$ 与 $(4,2)$，注意 $(2,5)$ 距离 $(2,2)$ 的曼哈顿距离为 $3$，无法被覆盖）

o....
.#..o
.....
.o...

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m,k\le 100$，$k\lt n\times m$，$1\le x_i\le n$，$1\le y_i\le m$，且没有重复的干员坐标。

• 子任务 1（30 分）：保证 $k=1$。
• 子任务 2（30 分）：保证 $k=n\times m-1$。
• 子任务 3（40 分）：没有特殊限制。

可以思考一下数据范围大了怎么做。