Problem Description

As a historian, Professor JOI is studying the IOI Kingdom that once existed.

According to past research, the IOI Kingdom is a rectangular area divided into a grid with $H$ rows and $W$ columns. The capital of the IOI Kingdom was surrounded by walls used for defense.

The walls surrounding the capital have the following shape. A wall has a value called its "size". A wall of size $s$ ($s \ge 3$) means the frame part that remains after removing an inner $(s-2) \times (s-2)$ square region from an $s \times s$ square region.

The investigation shows that the size of the wall surrounding the capital is at least $L$. In addition, it is known that there are some cells in the IOI Kingdom where there is no wall.

For further study, Professor JOI wants to know how many different walls are possible.

Task

Given the size of the IOI Kingdom, the minimum wall size, and the information about cells that are known to have no wall, write a program to compute how many walls are possible.

Input Format

Read the following data from standard input.

• The first line contains four space-separated integers $H, W, L, P$. This means the IOI Kingdom is a rectangular area with $H$ rows and $W$ columns, the wall size is at least $L$, and it is known that there are $P$ cells where no wall exists.
• In the next $P$ lines, the $i$-th line ($1 \le i \le P$) contains two space-separated integers $A_i, B_i$. This means it is known that the cell at row $A_i$ from top to bottom and column $B_i$ from left to right in the IOI Kingdom has no wall.

Output Format

Output one line to standard output containing one integer, which is the number of possible walls.

5 5 3 2
2 2
4 3

4

7 8 4 3
2 2
3 7
6 5

13

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

7050792912

Hint

Sample Explanation 1

In this sample, there are 4 possible walls as follows. The cells marked with × are the cells that are known to have no wall.

:::align{center} :::

Constraints

All input data satisfy the following conditions:

• $1 \le H \le 4000$.
• $1 \le W \le 4000$.
• $3 \le L \le H$ and $3 \le L \le 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$).
• $(A_i, B_i) \ne (A_j, B_j)$ ($1 \le i < j \le P$). (That is, the positions of the cells known to have no wall are all distinct.)

Subtasks

Subtask 1 [4 points]

Satisfies the following conditions:

• $H \le 500$.
• $W \le 500$.

Subtask 2 [16 points]

• Satisfies $0 \le P \le 10$.

Subtask 3 [80 points]

No additional constraints.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5