UOJ Logo Universal Online Judge

UOJ

#355. 【JOISC2017】Cultivation

附件下载 统计

小M家有一个 $W\times H$ 的农场。

每年开春的时候,小M会在农场的 $n$ 个位置撒下种子。

每天,小M可以选择一个当天的风向(东,南,西或者北),所有的种子会被风带着朝着风向移动一格。一旦一个种子在某个时刻到达了某个格子,那么之后的每个时刻这个格子都会有一个种子。

最少几天小M可以把所有农场都撒上种子。

输入格式

第一行两个整数 $W,H$,意义如题面所述。

第二行一个整数 $n$。

接下来 $n$ 行,每行两个整数 $x_i,y_i$,表示第$i$个种子的位置。

输出格式

一行一个整数,表示答案。

样例一

input

3 4
3
1 2
1 4
2 3

output

3

样例二

input

4 4
4
1 1
1 4
4 1
4 4

output

4

限制与约定

对于所有数据,

$1\le n\le 300,1\le W,H\le 10^9,1\le x_i \le W,1\le y_i\le H,(x_i,y_i)\not=(x_j,y_j)(1\le i < j \le n)$

子任务 分值 $W$ $H$ $n$
1 5 $\le 4$ $\le 4$
2 10 $\le 40$ $\le 40$
3 15 $\le 40$
4 30 $\le 25$
5 20 $\le 100$
6 20 $\le 300$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载