0652 - 開拓 (Cultivation)

21XX 年，IOI 星の住人は新たに発見された惑星に移住することになった．

移住先の惑星には縦 R 行，横 C 列のマス目状に区切られた畑があり，畑の縦方向は南北方向に平行であり，横方向は東西方向に平行である．北から i 行目，西から j 列目にあるマスをマス (i, j) と呼ぶ．畑の北西の隅のマスはマス (1, 1) であり，南東の隅のマスはマス (R, C) である．毎年，IOI 星の住人は，その年に畑に吹く風の向きを東西南北のいずれかに設定する．

移住先で農業を行うため，移住先にある畑いっぱいに JOI 草を生息させることになった．移住開始時の春，畑のうち N マスには JOI 草が自生している．

JOI 草は風によって生息圏を広げる．毎年夏になると，IOI 星の住人が設定した風の方向に種子を飛ばす．飛んだ種子はその風の向きに 1 マス進んた場所に着地する．その場所が畑のマスであり，かつ，そのマスがまだ JOI 草の生息圏でないなら，翌年の春にそのマスは JOI 草の生息圏となる．すでに JOI 草の生息圏となっているマスが，その後，JOI 草の生息圏でなくなることはない．

風の向きをうまく設定することで，畑のすべてのマスを JOI 草の生息圏にするためにかかる年数の最小値を求めたい．

課題

風の向きをうまく設定することで，畑のすべてのマスを JOI 草の生息圏にするためにかかる年数の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には 2 個の整数 R, C が空白を区切りとして書かれている．これらは畑が縦 R 行，横 C 列のマス目状に区切られていることを表す．
• 2 行目には整数 N が書かれている．これは移住開始時の春に，JOI 草が自生しているマスの個数を表す．
• 続く N 行のうちの i 行目（1 ≤ i ≤ N）には 2 個の整数 S_i, E_i が空白を区切りとして書かれている．これは移住開始時の春に，マス (S_i, E_i) に JOI 草が自生していることを表す．

出力

標準出力に，風の向きをうまく設定することで，畑のすべてのマスを JOI 草の生息圏にするためにかかる年数の最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 ≤ N ≤ 300．
• 1 ≤ R ≤ 1 000 000 000．
• 1 ≤ C ≤ 1 000 000 000．
• 1 ≤ S_i ≤ R (1 ≤ i ≤ N)．
• 1 ≤ E_i ≤ C (1 ≤ i ≤ N)．
• 移住開始時の春に，JOI 草が自生していない畑のマスがある．
• (S_i, E_i) ≠ (S_j, E_j) (1 ≤ i < j ≤ N)．

小課題

この課題では小課題は全部で 6 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題1 [5 点]

• R ≤ 4．
• C ≤ 4．

小課題2 [10 点]

• R ≤ 40．
• C ≤ 40．

小課題3 [15 点]

• R ≤ 40．

小課題4 [30 点]

• N ≤ 25．

小課題5 [20 点]

• N ≤ 100．

小課題6 [20 点]

• 追加の制限はない．

入出力例

入力例 1

3 4
3
1 2
1 4
2 3

出力例 1

3

入力例 1 では，移住開始時の春に以下のように JOI 草が自生している．

	0		0
		0

畑の様子．‘0’ は移住開始時の春にJOI 草が自生しているマスを表す．

この入力例では，3 年間の畑に吹く風の向きを西，南，南の順番に設定することで，3 年後の春にすべてのマスが JOI 草の生息圏となる．下の表の数値は，何年後の春に各マスが JOI 草の生息圏となるかを表している．これが最小の年数である．

1	0	1	0
2	1	0	2
3	2	2	3

入力例 2

4 4
4
1 1
1 4
4 1
4 4

出力例 2

4