题目描述

$H$ 行 $W$ 列のマス目があります。このマス目の $i$ 行目 $j$ 列目のマスをマス $(i,\ j)$ と呼ぶことにします。
このマス目の上には $N$ 個の電球と $M$ 個のブロックが置かれていて、$i$ 個目の電球はマス $(A_i,\ B_i)$ に、$i$ 個目のブロックはマス $(C_i,\ D_i)$ に置かれています。一つのマスにある電球とブロックは合計で高々一つです。
全ての電球は、ブロックが置かれているマスに到達するまで届く光を上下左右の $4$ 方向に放ちます。電球が置かれているマス自身にも光が届くものとします。
マス目上のブロックの置かれていないマスのうち電球の光が届くものの数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

マス目上のブロックの置かれていないマスのうち、電球の光が届くものの数を出力せよ。

题目大意

题目描述

有一个 $H$ 行 $W$ 列的网格，定义 $(i,j)$ 是第 $i$ 行 $j$ 列的方格。

这个网格上有 $N$ 个灯泡和 $M$ 个障碍物，第 $i$ 个灯泡在 $(A_i,B_i)$ 处，第 $i$ 个障碍物在 $(C_i, D_i)$ 处。每个方格保证最多只有一个灯泡或障碍物。

每一个灯泡都会将光照向上下左右四个方向延伸，直至遇到障碍物或到达边界。灯泡所在的方格也会有光照。

请你计算，被光照照到且没有障碍物的方格有多少。

输入格式

第一行四个整数 $H$、$W$、$N$ 和 $M$。

接下来 $N$ 行，每行两个整数 $A_i$ 和 $B_i$ 表示第 $i$ 个灯泡的坐标。

接下来 $M$ 行，每行两个整数 $C_i$ 和 $D_i$ 表示第 $i$ 个障碍物的坐标。

输出格式

一行一个表示答案的整数。

3 3 2 1
1 1
2 3
2 2

7

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

8

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

24

提示

制約

• $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)$
• 入力はすべて整数

Sample Explanation 1

ブロックの置かれていないマスのうち、マス $(3,\ 2)$ を除いた全てのブロックに光が届きます。

Sample Explanation 2

ブロックの置かれていないマスのうち、電球の光が届くものは以下の $8$ 個です。 - マス $(1,\ 1)$ - マス $(1,\ 2)$ - マス $(1,\ 3)$ - マス $(1,\ 4)$ - マス $(2,\ 2)$ - マス $(3,\ 3)$ - マス $(3,\ 4)$ - マス $(4,\ 4)$

Sample Explanation 3

この場合、ブロックが置かれていないマスには全て光が届きます。