题目思路

思路：二分答案 + BFS

想要最大化 从 $(sx, sy)$ 到 $(tx, ty)$ 的所有路径中，和所有土豆最近的距离，假设我们设定距离为 $d$ ，则和任意一个土豆的距离小于 $d$ 的点都可以看成不可走的点。所以二分这个 $d$ ，然后 $check$ 是否满足要求。

单调性证明

如果 $d$ 满足，那么 $d - 1$ 必然满足，但是 $d + 1$ 不一定满足，所以这部分就具有单调性，那么通过二分答案来解决该问题就具有了正确性。

题目描述：

小美是一个农民，他有一片 $n \times m$ 大小的田地，共 $n$ 行 $m$ 列，其中行和列都用从 $1$ 开始的整数编号，田地中有 $k$ 个格子中埋有土豆。我们记第 $a$ 行第 $b$ 列的格子为 $(a, b)$ 。小美现在位于 $(x1, y1)$ ，他想要移动到 $(x2, y2)$ 处去收菜，但是他不想阻碍自己土地里土豆的生长情况，所以他不想在移动过程中碰到土豆。

小美每次移动可以移动到与他所处格子的相邻的一格中，形式化地说，如果小美位于 $(x, y)$ ，则小美可以移动到 $(x-1, y)$ ， $(x+1, y)$ ， $(x, y-1)$ ， $(x, y+1)$ 的格子之一，但小美不能移动到田地之外。

小美想要在移动过程中，离这些土豆越远越好，而不是走最短路径。

这里定义两个格子之间的距离为曼哈顿距离，即格子 $(a, b)$ 和 $(c, d)$ 之间的距离是 $|a-c|+|b-d|$ 。

小美想知道，移动中与土豆之间距离的最小值最大可能是多少。

请注意，如果无论小美如何移动，都会进入一个有土豆的格子的话，这个最大可能值为 $0$ 。

输入描述

第一行三个整数 $n$， $m$ ， $k$ ，分别表示田地的行数，列数和土豆个数。

接下来 $k$ 行，每行两个整数 $p$ ， $q$ ，表示一个土豆放置在格子 $(p, q)$ 中。任意两土豆的放置位置不同。

接下来一行四个整数 $x1$ ， $y1$， $x2$ ， $y2$ ，表示小美的出发位置和目的位置。保证小美的出发位置和目的位置上没有土豆。

对于全部数据，

$1 \le n, m \le 500$ ，

$n \times m \ge 3$，

$1 \le k \le min\{n \times m-2, 400\}$ ，

$1 \le p, x1, x2 \le n$ ，

$1 \le q, y1, y2 \le m, (x1, y1) ≠ (x2, y2)$ ，

保证 $(x1, y1)$ 和 $(x2, y2)$ 中没有土豆，并且一个格子中最多放置一个土豆。

输出描述

输出一行一个整数，表示移动过程中与土豆之间距离的最小值的可能最大值。

样例

输入

5 6 2
2 1
2 3
1 1 5 1

输出

1