開拓 (Cultivation)
题意翻译
#「JOISC 2017 Day 1」开荒者
## 题目描述
**题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day1 T1「[開拓](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d1.pdf)（[Cultivation](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d1-en.pdf)）」**
开荒者要让一片长方形的平原长满草。这个长方形可视为 $R$ 行 $C$ 列的正方形网格，底平行于南北方向，高平行于东西方向。我们用 $(1,1)$ 表示网格的西北角，$(R,C)$ 表示网格的东南角。开始时有且只有 $N$ 个网格内长有野草，其余网格内既没有草也没有草籽。开荒者们可以控制这片平原上的风往东、西、南、北四个方向中的一个方向吹。
每年夏天，草会制造草籽。开荒者们会选定当年夏天的风向。所有草籽会被风扬起，并根据风向移动一格。来年春天，有草籽降落的网格就会有草萌发。假设草不会枯萎。
我们假设不会有草籽从平原外飘进平原内，飘出网格的草籽不会发芽。试求：让这片平原长满草最少需要几年。
## 输入格式
第一行有两个整数 $R, C$，用空格分隔。
第二行有一个整数 $N$。
在接下来的 $N$ 行中，第 $i$ 行 $(1\le i\le N)$ 有两个整数 $S_i, E_i$，表示 $(S_i, E_i)$ 长有野草。
## 输出格式
一个整数，表示在理想方案下，这片平原长满草最少需要的年数。
## 样例
#### 样例输入 1
```plain
3 4
3
1 2
1 4
2 3
```
#### 样例输出 1
```plain
3
```
#### 样例解释 1
一种最佳方案是三年的风向分别为东、南、南。
#### 样例输入 2
```plain
4 4
4
1 1
1 4
4 1
4 4
```
#### 样例输出 2
```plain
4
```
## 限制与提示
对于所有数据，$1\le N\le 300, 1\le R, C\le 10^9, 1\le S_i \le R, 1\le E_i\le C, (S_i, E_i)≠(S_j, E_j)(1\le i<j\le N)$。
|Subtask #|分值|$R,C$|$N$|
|-|-|-|-|
|1|5|$R,C\le 4$|$N\le 16$|
|2|10|$R,C\le 40$|-|
|3|15|$R\le 40$|-|
|4|30|-|$N\le 25$|
|5|20|-|$N\le 100$|
|6|20|-|-|
感谢 Planet6174 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/joisc2017/tasks/joisc2017_a