说明

身为历史学家的 JOI 教授，正在研究曾经存在的 IOI 王国。

根据过去的调查，IOI 王国是一个被划分为 $H$ 行 $W$ 列网格的长方形区域。IOI 王国的首都被用于防御的城墙所环绕。

环绕 IOI 王国首都的城墙具有以下形状。城墙定义了一个称为“大小”的值。大小为 $s$ ($s \ge 3$) 的城墙，是指从一个 $s \times s$ 的正方形区域中，挖去其内部一个 $(s-2) \times (s-2)$ 的正方形区域后剩下的边框部分。

调查表明，环绕首都的城墙大小至少为 $L$。此外，已知 IOI 王国的某些网格上没有城墙存在。

JOI 教授为了进一步研究，想知道可能的城墙有多少种。

任务

给定 IOI 王国的尺寸、城墙大小的最小值以及已知没有城墙存在的网格信息，请编写一个程序，计算可能的城墙有多少种。

输入格式

从标准输入读取以下数据。

• 第一行包含四个以空格分隔的整数 $H, W, L, P$。这表示 IOI 王国是一个 $H$ 行 $W$ 列的长方形区域，城墙大小至少为 $L$，并且已知有 $P$ 个网格上没有城墙存在。
• 接下来的 $P$ 行中，第 $i$ 行 ($1 \le i \le P$) 包含两个以空格分隔的整数 $A_i, B_i$。这表示已知 IOI 王国从上往下第 $A_i$ 行、从左往右第 $B_i$ 列的网格上没有城墙存在。

输出格式

向标准输出输出一行，包含一个整数，表示可能的城墙有多少种。

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

提示

样例解释 1

在这个样例中，可能的城墙有以下 4 种。其中，用 × 标记的网格是已知没有城墙存在的网格。

:::align{center} :::

数据范围

所有输入数据满足以下条件：

• $1 \le H \le 4000$。
• $1 \le W \le 4000$。
• $3 \le L \le H$ 且 $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$)。（即已知无城墙的网格位置互不相同）

子任务

子任务 1 [4 分]

满足以下条件：

• $H \le 500$。
• $W \le 500$。

子任务 2 [16 分]

• 满足 $0 \le P \le 10$。

子任务 3 [80 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成