도시의 화재

Berland의 수도는 같은 크기의 정사각형 블록들로 이루어진, 크기가 n × m인 직사각형 모양이다.

불이 났다!

k + 1개의 블록에 (k + 1 ≤ n·m) 불이 붙었다고 알려져 있다. 이 블록들은 발화 지점이다. 또한 이 지점들 중 k개의 위치는 알려져 있고 하나의 위치는 알려져 있지 않다. k + 1개의 위치는 모두 서로 다르다.

불은 다음과 같이 번진다. 화재가 발생한 지 영 분째에는 이 k + 1개의 발화 지점만 타고 있다. 그다음부터 매분 불타고 있는 블록과 이웃한 모든 블록으로 불이 번진다. 블록은 이 문제에서 소요되는 시간을 초과할 만큼 오랫동안 탄다고 간주할 수 있다. 현재 블록과 변 또는 모서리가 맞닿은 블록이 이웃한 블록이다.

Berland Fire Deparment는 불이 도시 전체를 밝히는 데 걸리는 최소 시간을 추정하려고 한다. k개 블록(발화 지점)의 위치는 알려져 있으며, (k + 1)-th는 다른 어떤 블록에도 위치할 수 있음을 기억하라.

Help Berland Fire Department는 불이 도시 전체를 밝히는 데 걸리는 최소 시간을 추정한다.

첫째 줄에는 세 정수 n, m, k가 (1 ≤ n, m ≤ 109, 1 ≤ k ≤ 500) 주어진다.

이어지는 k개의 각 줄에는 두 정수 xi와 yi가 (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) 주어진다. 이는 i-th 발화 지점의 좌표이다. 모든 발화 지점의 위치가 서로 다름이 보장된다.

불이 도시 전체를 밝히는 데 걸리는 최소 시간을 분 단위로 출력한다.

첫 번째 예제에서 마지막 블록의 좌표는 (4, 4)일 수 있다.

두 번째 예제에서 마지막 블록의 좌표는 (8, 3)일 수 있다.