Boundless Boxes

2008 ACM ICPC 세계 대회에 등장한 화가 Peer를 기억하시나요? Peer는 단색화(monochromy) 기법의 창시자 중 한 명으로, 그의 그림은 저마다 하나의 색만 쓰되 명암(shade)을 여러 단계로 달리합니다. 또한 그는 단순한 기하학적 도형을 즐겨 사용합니다.

몇 달 전까지 Peer는 캔버스의 바깥에서 안쪽으로 삼각형을 그렸습니다. 이제 삼각형은 유행이 지나고 정사각형이 유행하면서, 그의 최신 작품은 안쪽에서 바깥쪽으로 그려 나가는 동심(同心) 정사각형을 사용합니다! Peer는 완전한 정사각형 격자로 나뉜 직사각형 캔버스에서 시작합니다. 그는 몇 개의 격자 칸을 중심 씨앗(seed) 으로 골라 가장 어두운 명암으로 칠합니다. 각 씨앗에서 시작해 그것을 감싸는 한 단계 밝은 명암의 더 큰 정사각형을 칠하고, 이를 다시 감싸는 더 큰 정사각형을 반복해서 칠하며 캔버스 전체가 덮일 때까지 계속합니다. 각 정사각형은 자신이 감싸는 정사각형보다 정확히 격자 한 칸 크고 한 단계 밝습니다. 정사각형들이 겹치는 칸은 항상 더 어두운 명암으로 칠합니다.

그림 1: 여섯 단계의 명암을 사용한 Peer의 최근 작품 예시.

바꿔 말하면, 한 칸의 명암 번호는 그 칸에서 가장 가까운 씨앗까지의 체비쇼프(Chebyshev) 거리에 $1$을 더한 값입니다. 어떤 칸이 가장 가까운 씨앗 $(r_i, c_i)$ 로부터 거리 $d = \max(|r - r_i|,\ |c - c_i|)$ 만큼 떨어져 있으면 그 칸의 명암 번호는 $d + 1$ 이며, 가장 어두운 명암이 $1$ 입니다. 필요한 명암의 개수는 캔버스 전체에 나타나는 가장 큰 명암 번호입니다.

캔버스의 크기와 씨앗들의 위치가 주어질 때, 이 그림에 필요한 명암의 개수를 구하는 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 공백으로 구분된 세 정수 $m$, $n$, $s$가 적힌 한 줄로 시작합니다. 캔버스는 정확히 $m \times n$개의 격자 칸으로 이루어지며($1 \le m, n \le 1000$), 세로로 $1$부터 $m$까지, 가로로 $1$부터 $n$까지 번호가 매겨집니다. 그림에는 $s$개의 씨앗 칸이 사용되며($1 \le s \le 1000$), 이어지는 $s$개의 줄에 각각 두 정수 $r_i$와 $c_i$($1 \le r_i \le m$, $1 \le c_i \le n$)로 씨앗 칸의 행과 열이 주어집니다. 모든 씨앗은 캔버스 안에 있습니다.

연속한 테스트 케이스는 빈 줄로 구분됩니다. 0 0 0 이 적힌 줄은 입력의 끝을 나타내며 처리하지 않습니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다: 해당 그림에 필요한 서로 다른 명암의 개수입니다.