矩形剪裁

题目描述

Y 同学正在研究一个网格图问题。他有一个包含 $H$ 行 $W$ 列的巨大网格。记从上往下数第 $r$ 行、从左往右数第 $c$ 列的格子为 $(r,c)$。

网格中的每个格子要么是黑色的，要么是白色的。已知网格中有 $N$ 个格子被涂成了黑色，分别是 $(R_1, C_1), (R_2, C_2), \ldots, (R_N, C_N)$，其余的 $H \times W - N$ 个格子则全部是白色的。

Y 同学的目标是找出在这个网格中，有多少个大小为 $h \times w$（即包含 $h$ 行 $w$ 列）的矩形区域，满足该区域内的所有格子都是白色的。

形式化地，你需要求出满足以下所有条件的整数对 $(r_0, c_0)$ 的数量：

1. $1 \le r_0 \le H - h + 1$
2. $1 \le c_0 \le W - w + 1$
3. 对于所有满足 $0 \le i < h$ 且 $0 \le j < w$ 的整数对 $(i, j)$，格子 $(r_0 + i, c_0 + j)$ 都是白色的。

输入格式

第一行包含五个用空格分隔的整数 $H, W, h, w, N$，分别表示网格的总行数、总列数，目标矩形区域的行数、列数，以及黑色格子的数量。

接下来 $N$ 行，每行包含两个整数 $R_k, C_k$，表示第 $k$ 个黑色格子所在的行和列。

输出格式

输出一行一个整数，表示网格中满足条件的全白矩形区域的数量。

样例

样例输入 #1

3 4 2 2 3
1 3
2 4
3 1

样例输出 #1

2

样例输入 #2

4 4 3 2 2
2 2
3 4

样例输出 #2

0

样例输入 #3

449 449 3 14 0

样例输出 #3

194892

样例输入 #4

31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

样例输出 #4

12

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le h \le H \le 10^9$
• $1 \le w \le W \le 10^9$
• $0 \le N \le 2 \times 10^5$
• $1 \le R_k \le H$
• $1 \le C_k \le W$
• 黑格子的坐标互不相同，即对于 $k_1 \ne k_2$，有 $(R_{k_1}, C_{k_1}) \ne (R_{k_2}, C_{k_2})$。