题目描述

在 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 草所需的最少年数。

3 4
3
1 2
1 4
2 3

3

4 4
4
1 1
1 4
4 1
4 4

4

提示

样例 1 解释

在样例输入 1 中，以下格子在移民第一年的春季已种有 JOI 草。

x 0 x 0
x x 0 x
x x x 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 完成