30027번 - 비밀의 화원

문제

유진이는 어렸을 적부터 자신만의 화원에서 꽃을 가꾸는 것을 꿈꿔왔다. 많은 세월이 지나고, 꿈을 이루기 위해 열심히 노력한 유진이는 마침내 자신만의 화원을 장만하게 되었다.

유진이의 화원은 $N$행 $M$열의 격자로 생각할 수 있는데, 아직은 격자의 각 칸에 아무것도 심어져 있지 않다. 유진이는 격자에서 서로 다른 $K$개의 칸을 골라서 꽃을 한 송이씩 심었다. 유진이가 심은 꽃은 영원히 시들지 않고, 하루가 지날 때마다 상하좌우로 인접한 칸에 추가로 꽃을 피운다.

유진이는 화원이 꽃으로 가득 찰 때를 기다리고 있다. 그때가 되면 화원에 친구를 초대해 차를 마시며 이야기를 나눌 것이다. 유진이가 꽃을 심고 난 이후로 화원의 모든 칸에 꽃이 피어나려면 최소 며칠이 지나야 하는지 구해보자.

입력

첫째 줄에 정수 $N(1\le N\le 4,000円)$과 정수 $M(1\le M\le 100,000円)$과 정수 $K(1\le K\le\min(N\times M,1,000円))$가 공백으로 구분되어 주어진다.

둘째 줄부터 $K$개의 줄에 유진이가 꽃을 심은 칸의 위치를 의미하는 정수 $i,j(1\le i\le N;1\le j\le M)$가 공백으로 구분되어 주어진다. $i,j$는 격자의 $i$번째 행, $j$번째 열을 의미한다.

출력

화원의 모든 칸에 꽃이 피어나기까지 최소 며칠이 지나야 하는지 출력한다.

제한

힌트