# 麦田选址

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

村长计划开辟一片正方形麦田，让它成为村庄的一处整齐景观。候选区域内已有一些建筑，麦田不能占用这些位置。请找出能够种植的最大正方形。

## 形式化问题描述

给定一个 $n$ 行 $m$ 列的网格，以及 $k$ 条建筑位置记录 $(x_i,y_i)$ .记录可能重复，同一位置重复出现仍只表示该格有建筑。

选择连续的 $s$ 行和连续的 $s$ 列作为麦田，要求其中没有任何建筑。求最大的整数边长 $s$ ；如果没有可用方格，输出 $0$ .

## 输入格式

第一行三个整数 $n,m,k$ .接下来 $k$ 行，每行两个整数 $x_i,y_i$ ，表示第 $x_i$ 行、第 $y_i$ 列有建筑。

## 输出格式

输出一个整数，表示最大边长。

## 样例 1

### 输入

```text
5 7 3
1 1
1 3
5 7
```

### 输出

```text
4
```

### 解释

选择第 $2$ 到 $5$ 行、第 $2$ 到 $5$ 列，可以得到边长为 $4$ 的麦田。边长为 $5$ 时必须覆盖全部五行，而任意连续五列都会包含至少一个建筑。

![五行七列的网格，建筑位于1行1列、1行3列、5行7列，框出2至5行和2至5列的四阶方形麦田](assets/largest-square.svg)

图 1：带叉号的格子表示建筑，粗框和浅色区域表示一块合法麦田。

## 样例 2

### 输入

```text
2 2 4
1 1
1 2
2 1
1 2
```

### 输出

```text
1
```

### 解释

位置 $(1,2)$ 被重复记录，实际只有三个格子被占用，剩余一格可以种植。

## 样例 3

### 输入

```text
2 2 4
1 1
1 2
2 1
2 2
```

### 输出

```text
0
```

### 解释

四个格子都有建筑，答案为零。

## 数据范围与保证

- $1\le n,m\le100000$ ，$0\le k\le200$ .
- $1\le x_i\le n$ ，$1\le y_i\le m$ ；建筑记录允许重复。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |