AT_joisc2017_a.開拓 (Cultivation)

#「JOISC 2017 Day 1」开荒者

题目译自 JOISC 2017 Day1 T1「開拓（Cultivation）」

开荒者要让一片长方形的平原长满草。这个长方形可视为 $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

3 4
3
1 2
1 4
2 3

样例输出 1

3

样例解释 1

一种最佳方案是三年的风向分别为东、南、南。

样例输入 2

4 4
4
1 1
1 4
4 1
4 4

样例输出 2

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 提供的翻译