一家公司希望购买一台正方形的清洁机器人来清洁一个矩形的房间。房间的部分区域有障碍物。

市面上有各种不同尺寸的机器人。如果机器人的任何部分都不与障碍物重叠，它就可以在房间内进行水平和垂直移动。机器人无法改变方向，因此其移动始终与坐标轴平行。较大的机器人工作效率更高，但更容易受到障碍物的阻碍。机器人必须始终完全处于房间内，且不能有任何部分超出矩形的边缘。

公司能购买的能够清洁房间内所有未被障碍物占据的方格的机器人，其边长最大是多少？

输入格式

第一行包含三个整数 $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

样例输出 1

2