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)。