CF845E Fire in the City

Berland 的首都是一个由 $n\times m$ 个同样大小的正方形区块组成的矩形。 着火了！ 已知有 $k+1$ 个区块着火（$k+1 \leq n \cdot m$）。这些区块是“起火中心”。此外，这 $k+1$ 个起火中心中，有 $k$ 个的位置已知，剩下一个位置未知。所有 $k+1$ 个位置互不相同。 火势蔓延的过程如下：在第 $0$ 分钟时，只有这 $k+1$ 个起火中心着火。之后每过一分钟，所有与正在燃烧的区块相邻（通过边或角相接）的区块也会被点燃。你可以认为每个区块会燃烧很久，这个时间远超出题目的考虑范围。相邻的区块指的是通过边或角与当前区块接触的区块。 Berland 消防局想要估计点燃整个城市所需的最短时间。注意，$k$ 个起火中心的位置已知，第 $k+1$ 个“起火中心”可以位于任意未被其他起火中心占据的区块上。 请帮助 Berland 消防局估算点燃整个城市所需的最短时间。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 10^{9}$，$1 \leq k \leq 500$）。 接下来的 $k$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i \leq n$，$1 \leq y_i \leq m$），表示第 $i$ 个起火中心的坐标。保证所有起火中心的位置互不相同。

输出点燃整个城市所需的最短时间（单位：分钟）。

在第一个样例中，最后一个起火点可以选在坐标 $(4,4)$。 在第二个样例中，最后一个起火点可以选在坐标 $(8,3)$。 由 ChatGPT 5 翻译