CF845E.Fire in the City

The capital of Berland looks like a rectangle of size n × m of the square blocks of same size.

Fire!

It is known that k + 1 blocks got caught on fire (k + 1 ≤ n·m). Those blocks are centers of ignition. Moreover positions of k of these centers are known and one of these stays unknown. All k + 1 positions are distinct.

The fire goes the following way: during the zero minute of fire only these k + 1 centers of ignition are burning. Every next minute the fire goes to all neighbouring blocks to the one which is burning. You can consider blocks to burn for so long that this time exceeds the time taken in the problem. The neighbouring blocks are those that touch the current block by a side or by a corner.

Berland Fire Deparment wants to estimate the minimal time it takes the fire to lighten up the whole city. Remember that the positions of k blocks (centers of ignition) are known and (k + 1)-th can be positioned in any other block.

Help Berland Fire Department to estimate the minimal time it takes the fire to lighten up the whole city.

伯兰德的首都呈 $n \times m$ 的矩形，由大小相同的正方形街区构成。

着火了！

已知共有 $k+1$ 个街区起火（$k+1 \leq n \cdot m$），这些街区即为着火点。其中 $k$ 个着火点的位置已知，而第 $(k+1)$ 个着火点的位置未知。所有 $k+1$ 个着火点位置互不相同。

火灾蔓延方式如下：在第 $0$ 分钟，仅有这 $k+1$ 个着火点正在燃烧；此后每一分钟，火焰会蔓延至所有与当前正在燃烧的街区相邻的街区。你可以认为街区一旦开始燃烧，其燃烧时间足够长，远超本题所涉及的时间范围。所谓“相邻”，指两个街区在上下、左右或四个对角方向上直接接触（即共享一条边或一个顶点）。

伯兰德消防部门希望估算火焰烧遍整座城市的最短时间。注意：已知 $k$ 个着火点的位置，而第 $(k+1)$ 个着火点可置于其余任意一个未被占用的街区中。

请帮助伯兰德消防部门估算火焰烧遍整座城市的最短时间。

The first line contains three integers n, m and k (1 ≤ n, m ≤ 109, 1 ≤ k ≤ 500).

Each of the next k lines contain two integers x__i and y__i (1 ≤ x__i ≤ n, 1 ≤ y__i ≤ m) — coordinates of the i-th center of ignition. It is guaranteed that the locations of all centers of ignition are distinct.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 10^9$，$1 ≤ k ≤ 500$）。

接下来的 $k$ 行每行包含两个整数 $x_i$ 和 $y_i$（$1 ≤ x_i ≤ n$，$1 ≤ y_i ≤ m$），表示第 $i$ 个着火点的坐标。保证所有着火点的位置互不相同。

Print the minimal time it takes the fire to lighten up the whole city (in minutes).

输出火灾蔓延至整座城市所需的最短时间（单位：分钟）。

In the first example the last block can have coordinates (4, 4).

In the second example the last block can have coordinates (8, 3).

在第一个例子中，最后一个方块的坐标可以是 $(4,\,4)$。

在第二个例子中，最后一个方块的坐标可以是 $(8,\,3)$。