시험 기간 벼락치기

시험 기간이 되어 Ashley는 기말고사 벼락치기를 하러 즐겨 찾는 도서관으로 향한다.

도서관에는 공부 전용 층이 있고, 그 층에는 $r$개의 행과 $c$개의 열로 이루어진 테이블이 일정한 간격으로 놓여 있다. 각 테이블에는 학생 한 명만 앉을 수 있으며, 이미 도착해서 자리를 잡은 학생이 몇 명 있다.

이 층은 보통 매우 조용해서 근처 학생들의 소리가 들린다. 예를 들어 노트북 자판을 답답하게 두드리는 소리나 초조하게 다리를 떠는 소리가 들릴 수 있다. 구체적으로, 행 $i\_1$, 열 $j\_1$의 테이블에서 공부하는 학생과 행 $i\_2$, 열 $j\_2$의 테이블에서 공부하는 학생은 $\sqrt{(i\_1 - i\_2)^2 + (j\_1 - j\_2)^2} \le d$일 때에만 서로의 소리를 들을 수 있다.

Ashley는 빈 테이블 중에서 자신이 들을 수 있는 다른 학생의 수가 가장 적은 곳을 고르려 한다. Ashley가 최적의 테이블을 고를 때 들을 수 있는 학생 수의 최솟값을 구하시오.

첫 줄에 정수 $r$, $c$ ($2 \leq r, c \leq 10^9$), $d$ ($1 \leq d \leq 2\,500$), $n$ ($1 \leq n \leq 10^3$이고 $n \leq r \cdot c - 1$)이 주어진다.

다음 $n$개의 줄에는 학생이 앉아 있는 테이블의 행 $i$ ($1 \le i \le r$)와 열 $j$ ($1 \le j \le c$)가 각각 주어진다. 같은 테이블에 두 학생이 앉아 있는 경우는 없다.

Ashley가 최적의 테이블을 고를 때 들을 수 있는 학생 수의 최솟값을 한 정수로 출력한다.