题目描述

我们有一个 $H$ 行 $W$ 列的网格。设 $(i, j)$ 表示该网格中第 $i$ 行第 $j$ 列的方格。
网格上有 $N$ 个灯泡和 $M$ 个障碍物。第 $i$ 个灯泡位于方格 $(A_i, B_i)$，第 $i$ 个障碍物位于方格 $(C_i, D_i)$。每个方格上最多只能放置一个对象——灯泡或障碍物。
每个灯泡会向上、下、左、右四个方向发出光线，直到碰到一个障碍物为止，照亮光线经过的方格。有灯泡的方格也被认为是被照亮的。在没有障碍物的方格中，找到被灯泡照亮的方格的数目。

约束条件

• $1 \le H, W \le 1500$
• $1 \le N \le 5 \times 10^5$
• $1 \le M \le 10^5$
• $1 \le A_i \le H$
• $1 \le B_i \le W$
• $1 \le C_i \le H$
• $1 \le D_i \le W$
• $(A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)$
• $(C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)$
• $(A_i, B_i) \neq (C_j, D_j)$
• 输入中的所有值都为整数。

输入

从标准输入读入数据，输入格式如下：

$H$ $W$ $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $A_3$ $B_3$ $\hspace{15pt} \vdots$ $A_N$ $B_N$ $C_1$ $D_1$ $C_2$ $D_2$ $C_3$ $D_3$ $\hspace{15pt} \vdots$ $C_M$ $D_M$

输出

打印在没有障碍物的方格中被灯泡照亮的方格数目。

示例输入 1

3 3 2 1
1 1
2 3
2 2

示例输出 1

7

在没有障碍物的方格中，除了方格 $(3, 2)$，其余全部被照亮。

示例输入 2

4 4 3 3
1 2
1 3
3 4
2 3
2 4
3 2

示例输出 2

8

在没有障碍物的方格中，以下八个方格被照亮：

• 方格 $(1, 1)$
• 方格 $(1, 2)$
• 方格 $(1, 3)$
• 方格 $(1, 4)$
• 方格 $(2, 2)$
• 方格 $(3, 3)$
• 方格 $(3, 4)$
• 方格 $(4, 4)$

示例输入 3

5 5 5 1
1 1
2 2
3 3
4 4
5 5
4 2

示例输出 3

24

这种情况下，没有障碍物的所有方格都被照亮。