2390 「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\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)$。