P15820 [JOI 2015 Final] City Wall / Rampart

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.

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 one line to standard output containing one integer, which is the number of possible walls.

### 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