题目描述

有一个 $n$ 行 $m$ 列的网格。其中有 $k+1$ 个格子着火了。每个时刻，火会蔓延至相邻的格子（八联通）。现在给出其中 $k$ 个着火的格子，请确定第 $k+1$ 格子，使得网格被烧完的用时最短。

你只需要输出最短用时。

输入格式

第一行输入 $3$ 个整数 $n,m,k$，$1\le n,m\le 10^{9},1\le k\le 500$。

接下来 $k$ 行，每行两个整数 $x_i, y_i$，$1\le x_{i}\le n,1\le y_{i}\le m。表示第$i$ 个着火的格子坐标。

输出格式

一个整数表示网格被烧完的最短用时。

7 7 3
1 2
2 1
5 5

3

第 $k+1$ 个着火的格子为 $(4,4)$。

10 5 1
3 3

2

第 $k+1$ 个着火的格子为 $(8,3)$。