4402: 「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)$ 长有野草。

一个整数，表示在理想方案下，这片平原长满草最少需要的年数。

3 4
3
1 2
1 4
2 3

3