#214498. [JOISC 2017] 开荒者 / Cultivation

在 21XX 年，IOI 星球的居民计划移民至一颗新发现的星球。

这颗新星球上有一片田地，它是一个由 行和 列组成的矩形网格。列的方向与南北方向平行，行的方向与东西方向平行。从北向南数第 行、从西向东数第 列的格子被称为格子 。田地的西北角是格子 ，东南角是格子 。每年，IOI 星球的居民都会选择吹过田地的风的方向。风的方向可以是东、西、南或北之一。

为了在新星球上从事农业，他们将在田地的每个格子上种植“JOI 草”。在移民第一年的春季，田地中 个格子已种有 JOI 草。

JOI 草的覆盖范围会随风扩展。每年夏季，JOI 草的种子会被风吹向居民选定的方向。种子会向风的方向移动一个格子并落地。如果种子落在一个没有 JOI 草的格子上，那么该格子将在下一年春季长出 JOI 草。一旦一个格子长出 JOI 草，它在未来将一直保持有 JOI 草。

我们希望计算：如果适当调整风的方向，使田地中所有格子都长出 JOI 草所需的最少年数。

任务

编写一个程序，计算在适当调整风的方向的前提下，使田地中所有格子都长出 JOI 草所需的最少年数。

从标准输入读取以下数据：

• 第一行包含两个由空格分隔的整数 、。表示田地是一个 行 列的矩形网格。
• 第二行包含一个整数 ，表示在移民第一年春季，田地中已有 JOI 草的格子数。
• 接下来的 行中，第 行（）包含两个由空格分隔的整数 、。表示格子 在移民第一年春季已种有 JOI 草。

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

样例输入 1

3 4
3
1 2
1 4
2 3

样例输出 1

3

样例输入 2

4 4
4
1 1
1 4
4 1
4 4

样例输出 2

4

样例 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

数据范围

所有输入数据满足以下条件：

• 。
• 。
• 。
• （）。
• （）。
• 在移民第一年的春季，田地中至少存在一个没有 JOI 草的格子。
• （）。

子任务

共有 6 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [5 分]

• 。
• 。

子任务 2 [10 分]

• 。
• 。

子任务 3 [15 分]

• 。

子任务 4 [30 分]

• 。

子任务 5 [20 分]

• 。

子任务 6 [20 分]

无额外限制。

翻译由 Qwen3-235B 完成