성벽

역사학자 JOI 교수는 과거에 있었던 IOI 왕국을 연구한다.

지금까지의 조사에 따르면 IOI 왕국은 세로 $H$칸, 가로 $W$칸인 격자 모양이었고, 수도는 방어를 위해 성벽으로 둘러싸여 있었다.

수도를 둘러싼 성벽의 모양은 다음과 같다.

• 성벽에는 크기 $s$($s \ge 3$)가 있다.
• 크기가 $s$인 성벽은 $s \times s$ 정사각형 영역에서 안쪽 $(s-2) \times (s-2)$ 정사각형 영역을 뺀, 두께 한 칸짜리 테두리다.

다른 조사에 따르면 수도를 둘러싼 성벽의 크기는 $L$ 이상이었다. 또 몇몇 칸에는 오래된 나무가 서 있는데, 나무가 있는 칸에는 성벽이 없었다. 성벽은 테두리에만 놓이므로 테두리 안쪽에 있는 나무는 성벽을 막지 않는다.

JOI 교수는 이 사실을 바탕으로 있을 수 있는 성벽이 몇 가지인지 알고 싶어 한다. 크기가 같아도 위치가 다르면 서로 다른 성벽으로 센다.

왕국의 크기, 성벽의 최소 크기, 나무의 위치가 주어질 때 있을 수 있는 성벽의 가짓수를 구하는 프로그램을 작성하시오.

첫 줄에 정수 $H$, $W$, $L$, $P$가 공백으로 구분되어 주어진다. 왕국의 크기가 세로 $H$칸, 가로 $W$칸이고, 성벽의 최소 크기가 $L$, 나무의 개수가 $P$라는 뜻이다.

이어지는 $P$개의 줄에 나무의 위치 $A_i$, $B_i$가 공백으로 구분되어 주어진다. $i$번째 나무가 위에서 $A_i$번째 줄, 왼쪽에서 $B_i$번째 칸에 있다는 뜻이다.

첫 줄에 있을 수 있는 성벽의 가짓수를 출력한다.

• $1 \le H, W \le 4000$
• $3 \le L \le \min(H, W)$
• $0 \le P \le 100000$
• $1 \le A_i \le H$ ($1 \le i \le P$)
• $1 \le B_i \le W$ ($1 \le i \le P$)
• $i \ne j$이면 $(A_i, B_i) \ne (A_j, B_j)$