题目背景

1G, 2s, vattenfall

题目描述

Alexander 喜欢水。因此，他也就喜欢奔腾的流水。这也许能解释为什么他想要造一座属于自己的瀑布。想象一下，水流无尽地倾泻而下！

他找到了一面悬崖面，只要加上水，它就能成为理想的瀑布。该悬崖面可建模为一张 $R \times C$ 的网格，其中有 $N$ 个单元格上有岩壁突出物。Alexander 计划从上方向下倒水，使水沿着 $K$ 根竖直列流下。

水在网格中的扩散遵循如下规则：如果水正下方的单元格为空，则水向下扩散；如果正下方有岩壁，则水会向左、向右扩散；如果向左或向右的方向上有岩壁，则水在该方向不再扩散。这个规则同样适用于自上而下倒入的水。也就是说，如果把水倒入第 $i$ 列且顶行第 $i$ 列有岩壁，那么相当于也从上方向第 $i-1$ 列和第 $i+1$ 列倒水（前提是这些列仍在网格范围内）。

然而，Alexander 不想引发泛滥，因为那样最终所有的水都会静止不动。静止的水当然不如奔流的水来得令人兴奋。因此，他希望你编写一个程序，计算悬崖面底行中，有水的列数。

图 1：样例 1 和 2 的流动示意图。红色边框标记了悬崖面的末端。

输入格式

第一行包含两个整数 $R, C$（$1 \leq R, C \leq 10^9$），表示构成山体的行数与列数。

第二行包含两个整数 $K, N$（$1 \leq K, N \leq 10^5$），分别表示有水的列数与从山体中突出的岩壁数量。

接下来有 $K$ 行，其中第 $i$ 行给出一个数 $V_i$（$0 \leq V_i \leq C-1$），表示有水从网格上方沿第 $V_i$ 列流下。保证所有 $V_i$ 互不相同。

随后有 $N$ 行，其中第 $i$ 行包含两个整数 $A_i$（$1 \leq A_i \leq R-1$）与 $B_i$（$0 \leq B_i \leq C-1$），表示第 $i$ 个岩壁所在的行与列。上述位置两两不同。

输出格式

输出一个整数：网格底行中含有水的列数。

8 6
3 4
1
4
5
1 3
2 2
5 1
5 5

3

8 6
1 8
3
2 1
1 2
2 3
5 2
5 3
5 4
5 5
6 5

1

5 4
1 3
3
1 1
2 2
3 3

1

提示

子任务

本题采用捆绑测试。

子任务编号	分值	限制
$1$	$20$	$R \cdot C \leq 100$
$2$	$30$	任意两个岩壁不能在对角、水平或垂直方向上相邻接触。
$3$	$20$	任意两个岩壁不能在对角方向上相邻接触。
$4$	$30$	无额外限制。