Problem K: Escape of Lappin the Phantom Thief

Problem

怪盗ラッパンは宝石を盗みにやってきた。簡単に宝石を手にすることができたが、宝石にはセンサーが仕込まれており、警備ロボットに囲まれてしまった。

警備ロボットは宝石に向かって移動するように仕組まれている。センサーは簡単に外せそうになかったので、宝石を置いて逃走することにした。宝石をできるだけ警備ロボットから遠くに置いて、逃げるための時間稼ぎをすることにした。

敷地はn × mのマスからなる長方形の形をしていて、障害物はない。 k体の警備ロボットは、それぞれマス(x_i, y_i)(0 ≤ x_i ≤ n−1, 0 ≤ y_i ≤ m−1)に配置されており、上下左右のマスに単位時間で移動できる。 警備ロボットは宝石があるマスに最短経路で移動する。

敷地内に自由に宝石を置けるとき、1台以上の警備ロボットが宝石のあるマスに到達するまでにかかる移動時間の最大値を求めよ。

Input

n m k
x1 y1
x2 y2
...
xk yk

入力はすべて整数で与えられる。
1行目にn, m, kが空白区切りで与えられる。
2行目以降k行に警備ロボットのいるマスの座標(x_i, y_i)が空白区切りで与えられる。

Constraints

• 1 ≤ n, m ≤ 5 × 10⁴
• 1 ≤ k ≤ min(10⁵, n × m)
• 0 ≤ x_i ≤ n−1
• 0 ≤ y_i ≤ m−1
• 与えられる座標はすべて異なる

Output

警備ロボットが到達するまでに、最も時間がかかる場所への移動時間を1行に出力せよ。

Sample Input 1

20 10 1
0 0

Sample Output 1

28

Sample Input 2

20 10 2
0 0
17 5

Sample Output 2

15

Sample Input 3

20 10 3
0 0
17 5
6 9

Sample Output 3

11

Note

Link

 

---