일자 빗자루로 방 쓸기

코딩에 빠져 지내는 사이 방에 먼지가 쌓였다. 부모님이 알아차리기 전에 방을 쓸어야 한다.

방은 $N$행 $M$열 격자로 나타낸다. 각 칸에는 가구가 놓여 있거나, 비어 있어서 쓸어야 한다. 빈 칸은 적어도 하나 있다.

청소에는 일자 빗자루를 쓴다. 길이가 $X$인 일자 빗자루는 한 열에서 세로로 연속한 $X$칸을 덮는다. 한 번의 쓸기는 빗자루를 내려놓고 가로 방향으로 원하는 거리만큼 미는 것이며, 미는 거리는 0이어도 된다. 쓸기가 진행되는 동안 빗자루는 항상 방 안에 완전히 들어 있어야 하고, 빗자루가 덮는 $X$칸은 모두 비어 있어야 한다. 쓸기 도중 빗자루가 지나간 칸에서는 먼지가 사라진다.

빗자루는 길수록 좋으므로 방 전체를 쓸 수 있는 가장 긴 빗자루를 산다. 빈 칸이 모두 한 번 이상 쓸기에 포함되면 방을 전부 쓴 것이다. 빗자루 길이를 정한 다음에는 쓸기 횟수도 최소로 줄이려 한다.

첫 줄에 행의 수 $N$, 열의 수 $M$, 가구의 개수 $F$가 주어진다. ($1 \le N \le 2000$, $1 \le M \le 2000$, $1 \le F < NM$)

다음 $F$개의 줄에는 가구 하나의 행 번호 $r$과 열 번호 $c$가 주어진다. ($1 \le r \le N$, $1 \le c \le M$) 같은 좌표에 두 가구가 놓이는 경우는 없다.

첫 줄에 살 수 있는 가장 긴 빗자루의 길이를 출력한다.

둘째 줄에 그 빗자루로 빈 칸을 모두 쓸 때 필요한 쓸기 횟수의 최솟값을 출력한다.