시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 53 16 12 44.444%

문제

역사학자인 JOI 교수는 이전에 존재했던 IOI 왕국에 대해 연구하고 있다.

과거의 조사에 따르면, IOI 왕국은 세로 H 크기에 가로 W 크기이며, IOI 왕국의 수도는 방어를 위해 성벽으로 둘러싸여 있었다.

IOI 왕국의 수도를 둘러싸는 성벽은 다음과 같은 형태를 하고 있다:

  • 성벽의 크기 s(s ≥ 3)가 있다.
  • 크기 s의 성벽은 s × s의 정사각형 영역에서 안의 (s-2) × (s-2) 정사각형 영역을 제외한 테두리 모양을 하고 있다.

또 다른 조사에 의하면, 수도를 둘러싼 성벽의 크기는 L 이상이었다. 그리고 어떤 칸들에는 오래된 나무가 있는데, 나무가 있는 위치에는 성벽이 존재하지 않았음을 알고 있다.

JOI 교수는 이러한 사실들을 바탕으로 있을 수 있는 성벽의 가지 수를 알고 싶어한다. ㅣ 때, 성벽의 크기가 같더라도 위치가 다르면 서로 다른 성벽으로 간주한다.

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)

출력

첫 줄에 가능한 성벽의 가지 수를 출력한다.

예제 입력

5 5 3 2
2 2
4 3

예제 출력

4

예제 입력 2

7 8 4 3
2 2
3 7
6 5

예제 출력 2

13

예제 입력 3

4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530

예제 출력 3

7050792912

힌트

1번 예제에서 가능한 성벽은 아래 4가지이다. 나무는 x로 표시되어있다.

출처

Olympiad > 일본정보올림피아드 > JOI 2015 5번