모자이크

수찬이는 교실 벽면을 꾸미기 위해 큰 직사각형 도화지를 벽에 붙이고, 1cm 간격의 가로선과 세로선을 그어 정사각형 칸으로 나누었다. 각 칸을 같은 색으로 칠한 뒤 몇 칸이 잘못 칠해졌다는 사실을 알게 되었다.

잘못 칠해진 칸은 도화지와 같은 색의 정사각형 색종이를 붙여 가리려고 한다. 사용할 수 있는 색종이의 장수는 정해져 있으며, 모든 잘못 칠해진 칸을 가리기 위해 다음 조건을 지켜야 한다.

1. 사용하는 색종이는 모두 같은 크기의 정사각형이다.
2. 색종이의 크기는 한 변의 길이로 나타내며, 필요한 크기의 색종이를 구할 수 있다.
3. 모든 색종이는 도화지의 밑변에 맞추어 붙인다. 색종이는 서로 겹쳐 붙일 수 있다.

도화지의 행은 맨 아래에서 위쪽으로 1번부터, 열은 왼쪽에서 오른쪽으로 1번부터 번호가 매겨져 있다.

칸의 위치는 (행, 열)로 나타낸다. 그림처럼 잘못 칠해진 칸이 9개 있고 색종이 4장을 사용할 수 있다면, 필요한 색종이의 가장 작은 크기는 3cm이다.

도화지의 행과 열의 수, 사용할 색종이의 장수, 잘못 칠해진 칸들의 위치가 주어진다. 조건을 만족하면서 모든 잘못 칠해진 칸을 가릴 수 있는 색종이 한 변의 최소 길이를 구하라.

첫째 줄에 도화지의 행 수 R과 열 수 C가 빈칸을 사이에 두고 주어진다. R과 C는 모두 1,000,000 이하의 자연수이다.

둘째 줄에 사용할 색종이의 장수 P가 주어진다. P는 100 이하의 자연수이다.

셋째 줄에 잘못 칠해진 칸의 개수 K가 주어진다. K는 1,000 이하의 자연수이다.

다음 K개 줄에는 잘못 칠해진 칸의 위치가 한 줄에 하나씩 주어진다. 각 줄에는 행 번호와 열 번호가 빈칸을 사이에 두고 차례로 주어진다.

주어진 장수의 색종이를 사용해 잘못 칠해진 칸을 모두 가릴 수 있는 색종이의 최소 크기를 cm 단위의 자연수로 출력한다.