Problem Description

Professor JOI, a historian, is researching the once-existing Kingdom of IOI.

According to past investigations, the Kingdom of IOI was shaped like a rectangle divided into squares arranged in $H$ rows and $W$ columns. The capital of the Kingdom of IOI was surrounded by ramparts for defense.

The ramparts surrounding the capital had a property called "size". A rampart of size $s$ ($s \geq 3$) is defined as an $s \times s$ square area excluding the inner $(s - 2) \times (s - 2)$ square area.

The investigation revealed that the size of the ramparts surrounding the capital was at least $L$. It was also known that some squares in the Kingdom of IOI did not have ramparts.

Professor JOI wants to know how many possible configurations of the ramparts exist for further research.

Input Format

Read the following data from standard input:

• The first line contains integers $H$, $W$, $L$, and $P$ separated by spaces. This indicates that the Kingdom of IOI was divided into $H$ rows and $W$ columns, the size of the ramparts was at least $L$, and there were $P$ squares known to not have ramparts.
• The following $P$ lines contain integers $A_i$ and $B_i$ separated by spaces. This indicates that the square in the $A_i$-th row and $B_i$-th column did not have ramparts.

Output Format

Output a single line to standard output, which is an integer representing how many possible configurations of the ramparts exist.

Sample Input and Output

Sample Input #1

5 5 3 2
2 2
4 3

Sample Output #1

4

Sample Input #2

7 8 4 3
2 2
3 7
6 5

Sample Output #2

13

Sample Input #3

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

Sample Output #3

7050792912

Notes/Hints

Task

Given the size of the Kingdom of IOI, the minimum size of the ramparts, and the information about squares known not to have ramparts, write a program to determine how many possible configurations of the ramparts exist.

Constraints

All input data satisfies the following conditions:

• $1 \leq H \leq 4,000$.
• $1 \leq W \leq 4,000$.
• $3 \leq L \leq H$ and $3 \leq L \leq W$.
• $0 \leq P \leq 100,000$.
• $1 \leq A_i \leq H$ ($1 \leq i \leq P$).
• $1 \leq B_i \leq W$ ($1 \leq i \leq P$).
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \leq i < j \leq P$).

Subtasks

Subtask 1 [4 points]

Satisfies the following condition:

• $H \leq 500$.
• $W \leq 500$.

Subtask 2 [16 points]

• $0 \leq P \leq 10$ is satisfied.

Subtask 3 [80 points]

No additional constraints.

Sample Explanation 1

In this input example, the following $4$ possible configurations of the ramparts are considered. Squares marked with × are known not to have ramparts. - - - - - -

Sample Explanation 2

见题面 Input 部分

见题面 Output 部分