P13988 [PO Final 2023] 瀑布 / Waterfall

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$ 个岩壁所在的行与列。上述位置两两不同。

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

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 分值 | 限制 | |:-:|:-:|-------------| | $1$ | $20$ | $R \cdot C \leq 100$ | | $2$ | $30$ | 任意两个岩壁不能在对角、水平或垂直方向上相邻接触。 | | $3$ | $20$ | 任意两个岩壁不能在对角方向上相邻接触。 | | $4$ | $30$ | 无额外限制。 |