Fortress Wall

Time limit10sMemory limit512 MB

Summary

Count square one-cell-thick borders of size at least L that fit in an H by W grid without covering a tree.

Level: Medium7 of 10
Topics: Prefix sum, Matrix
Solved: No attempts yet

Problem

Professor JOI, a historian, studies the IOI Kingdom that existed long ago.

Earlier surveys say the IOI Kingdom was a grid $H$ cells tall and $W$ cells wide, and that its capital was ringed by a fortress wall for defense.

The wall around the capital had this shape.

A wall has a size $s$ with $s \ge 3$ .
A wall of size $s$ is an $s \times s$ square region with its inner $(s-2) \times (s-2)$ square region removed, so it is a border one cell thick.

Another survey says the size of the wall around the capital was at least $L$ . Some cells hold an old tree, and a cell with a tree held no wall. The wall occupies the border only, so a tree strictly inside the border does not block it.

Professor JOI wants to know how many walls are possible given these facts. Two walls of the same size in different positions count as different walls.

Given the size of the kingdom, the minimum size of the wall, and the positions of the trees, write a program that counts the possible walls.

Input

The first line contains the integers $H$ , $W$ , $L$ , $P$ separated by spaces. The kingdom is $H$ cells tall and $W$ cells wide, the minimum size of the wall is $L$ , and the number of trees is $P$ .

Each of the next $P$ lines contains the position of a tree, $A_i$ and $B_i$ , separated by a space. The $i$ -th tree stands in row $A_i$ from the top and column $B_i$ from the left.

Output

Print the number of possible walls on the first line.

Constraints

$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$ )
$(A_i, B_i) \ne (A_j, B_j)$ whenever $i \ne j$

Examples3

Example 1
Input
```
5 5 3 2
2 2
4 3
```
Expected output
```
4
```
Example 2
Input
```
7 8 4 3
2 2
3 7
6 5
```
Expected output
```
13
```

Example 3

Input

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

Expected output

7050792912