题目描述

一家公司希望购买一台方形清洁机器人，用于清洁一个矩形的房间。房间的某些部分存在障碍物。

有不同尺寸的机器人可供选择。每个机器人可以在房间内水平或垂直移动，前提是机器人的任何部分都不与障碍物相交。机器人无法改变方向，因此移动始终是轴对齐的。较大的机器人能更快地完成清洁任务，但也更容易被障碍物阻挡。机器人必须始终完全位于房间内部，任何部分都不能超出矩形边界。

请问该公司能够购买的最大机器人尺寸是多少，使得该机器人能够清洁房间内所有未被障碍物占据的方格？

输入格式

输入的第一行包含三个整数 $n$、$m$（$3 \le n, m$ 且 $n \cdot m \le 5 \cdot 10^6$）和 $k$（$0 \le k < n \cdot m$，$k < 10^6$），其中 $n$ 和 $m$ 是房间的尺寸（单位为英寸），$k$ 是障碍物的数量。

接下来的 $k$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i \le n$，$1 \le j \le m$）。这表示位于 $(i, j)$ 的 $1$ 英寸方格是障碍物。所有障碍物方格互不相同。

输出格式

输出一个整数，表示能够清洁整个房间的最大方形机器人的边长。如果不存在这样的机器人，则输出 $-1$。

10 7 1
8 3

2

提示

翻译由 DeepSeek V3.2 完成