P14382 [JOISC 2017] 开荒者 / Cultivation

在 21XX 年，IOI 星球的居民计划移民至一颗新发现的星球。 这颗新星球上有一片田地，它是一个由 $R$ 行和 $C$ 列组成的矩形网格。列的方向与南北方向平行，行的方向与东西方向平行。从北向南数第 $i$ 行、从西向东数第 $j$ 列的格子被称为格子 $(i, j)$。田地的西北角是格子 $(1, 1)$，东南角是格子 $(R, C)$。每年，IOI 星球的居民都会选择吹过田地的风的方向。风的方向可以是东、西、南或北之一。 为了在新星球上从事农业，他们将在田地的每个格子上种植“JOI 草”。在移民第一年的春季，田地中 $N$ 个格子已种有 JOI 草。 JOI 草的覆盖范围会随风扩展。每年夏季，JOI 草的种子会被风吹向居民选定的方向。种子会向风的方向移动一个格子并落地。如果种子落在一个没有 JOI 草的格子上，那么该格子将在下一年春季长出 JOI 草。一旦一个格子长出 JOI 草，它在未来将一直保持有 JOI 草。 我们希望计算：如果适当调整风的方向，使田地中所有格子都长出 JOI 草所需的最少年数。 **任务** 编写一个程序，计算在适当调整风的方向的前提下，使田地中所有格子都长出 JOI 草所需的最少年数。

从标准输入读取以下数据： - 第一行包含两个由空格分隔的整数 $R$、$C$。表示田地是一个 $R$ 行 $C$ 列的矩形网格。 - 第二行包含一个整数 $N$，表示在移民第一年春季，田地中已有 JOI 草的格子数。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含两个由空格分隔的整数 $S_i$、$E_i$。表示格子 $(S_i, E_i)$ 在移民第一年春季已种有 JOI 草。

向标准输出写入一行。该行输出包含在适当调整风的方向的前提下，使田地中所有格子都长出 JOI 草所需的最少年数。

### 样例 1 解释 在样例输入 1 中，以下格子在移民第一年的春季已种有 JOI 草。 ``` x 0 x 0 x x 0 x x x x x ``` 新星球上的田地；标有‘0’的格子在移民第一年的春季已种有 JOI 草。 在本样例输入中，若我们为前三年选择的风向依次为西、南、南，则三年后的春季所有格子都将长出 JOI 草。下表中的数字描述了每个格子在春季首次长出 JOI 草的年份。这是所需的最少年数。 ``` 1 0 1 0 2 1 0 2 3 2 2 3 ``` ### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 300$。 - $1 \le R \le 1\,000\,000\,000$。 - $1 \le C \le 1\,000\,000\,000$。 - $1 \le S_i \le R$（$1 \le i \le N$）。 - $1 \le E_i \le C$（$1 \le i \le N$）。 - 在移民第一年的春季，田地中至少存在一个没有 JOI 草的格子。 - $(S_i, E_i) \ne (S_j, E_j)$（$1 \le i < j \le N$）。 ### 子任务 共有 6 个子任务。每个子任务的得分及附加约束如下： **子任务 1 [5 分]** - $R \le 4$。 - $C \le 4$。 **子任务 2 [10 分]** - $R \le 40$。 - $C \le 40$。 **子任务 3 [15 分]** - $R \le 40$。 **子任务 4 [30 分]** - $N \le 25$。 **子任务 5 [20 分]** - $N \le 100$。 **子任务 6 [20 分]** 无额外限制。 翻译由 Qwen3-235B 完成