문제
역사학자인 KOI 교수는 이전에 존재했던 IOI 왕국에 대해 연구하고 있다. 과거의 조사에 따르면, IOI 왕국은 세로 H 크기에 가로 W 크기이며, IOI 왕국의 수도는 방어를 위해 성벽으로 둘러싸여 있었다.
IOI 왕국의 수도를 둘러싸는 성벽은 다음과 같은 형태를 하고 있다:
- 성벽의 크기 s(s ≥ 3)가 있다. - 크기 s의 성벽은 s × s의 정사각형 영역에서 안의 (s-2) × (s-2) 정사각형 영역을 제외한 테두리 모양을 하고 있다.
또 다른 조사에 의하면, 수도를 둘러싼 성벽의 크기는 L 이상이었다. 그리고 어떤 칸들에는 오래된 나무가 있는데, 나무가 있는 위치에는 성벽이 존재하지 않았음을 알고 있다.
KOI 교수는 이러한 사실들을 바탕으로 있을 수 있는 성벽의 가지 수를 알고 싶어한다. 이 때, 성벽의 크기가 같더라도 위치가 다르면 서로 다른 성벽으로 간주한다.
IOI 왕국의 크기와, 성벽의 최소 크기, 그리고 나무의 위치들이 주어졌을 때 가능한 성벽의 가지 수를 구하는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 정수 H, W, L, P가 공백으로 구분되어 주어진다. 이는 IOI 왕국의 크기가 세로 H, 가로 W이며 성벽의 최소 크기는 L, 나무의 개수가 P라는 뜻이다.
다음 P 개의 줄에 나무의 위치가 Ai, Bi가 공백으로 구분되어 주어진다. 이는 나무가 Ai번째 줄, Bi번째 칸에 있음을 의미한다.
그리고 다음 제약 사항을 만족한다:
1 <= H, W <= 4 000
3 <= L <= min(H, W)
0 <= P <= 100,000
1 <= Ai <= H (1 <= i <=P)
1 <= Bi <= W (1 <= i <= P)
(Ai, Bi) != (Aj, Bj) (1 <= i < j <= P)
출력
첫 줄에 가능한 성벽의 가지 수를 출력한다.
예제1
입력
5532
22
43
출력
4
예제2
입력
7843
22
37
65
출력
13
예제3
입력
4000400012344
11613028
5961892
37312606
7021530
출력
7050792912
힌트
출처
JOI 2014/2015 본선 5