← 返回题目列表

Codeforces · 845/E

E. 城市火灾

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

Berland 的首都看起来像一个大小为 n × m 的矩形,由相同大小的正方形块组成。

着火了!

已知 k + 1 个方块着火了 (k + 1 ≤ n·m)。这些块是点火中心。此外,这些中心的 k 个位置是已知的,而其中之一仍然未知。所有 k + 1 个位置都是不同的。

火灾按照以下方式进行:在火灾的零分钟内,只有这 k + 1 个点火中心正在燃烧。每隔一分钟,火就会蔓延到正在燃烧的街区的所有邻近街区。您可以考虑将块燃烧很长时间,以使该时间超过解决问题所需的时间。相邻块是那些与当前块的边或角接触的块。

Berland 消防局想要估计大火照亮整个城市所需的最短时间。请记住,k 个块(点火中心)的位置是已知的,并且第 (k + 1) 个块可以位于任何其他块中。

帮助 Berland 消防局估计大火照亮整个城市所需的最短时间。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 109, 1 ≤ k ≤ 500)。

接下来的 k 行包含两个整数 xi 和 yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) — 第 i 个点火中心的坐标。保证所有点火中心的位置是不同的。

输出

打印大火照亮整个城市所需的最短时间(以分钟为单位)。

示例

输入 #1

7 7 3
1 2
2 1
5 5

输出 #1

3

输入 #2

10 5 1
3 3

输出 #2

2

注意

在第一个示例中,最后一个块可以具有坐标 (4, 4)。

在第二个示例中,最后一个块可以具有坐标 (8, 3)。