亚历山大喜欢水。因此，他喜欢奔腾的流水也就不足为奇了。这或许可以解释为什么他想建造自己的瀑布。想象一下，水流源源不断地倾泻而下！

他找到了一处悬崖峭壁，他相信在加入一些水后，这里将成为完美的瀑布。悬崖面可以建模为一个 $R \times C$ 的网格，其中有 $N$ 个单元格有突出的岩石。亚历山大计划从上方倒水，使其在 $K$ 列中向下流动。

水在网格中的扩散遵循以下规则：如果水下方的单元格为空，水就会流向下方。如果下方有岩石阻挡，水会向左和向右扩散。如果左侧或右侧有岩石阻挡，水就不会向该方向扩散。这也适用于从上方倒入的水，即：如果水被倒入第 $i$ 列，且最顶行在第 $i$ 列有岩石，这就相当于水也从上方的第 $i - 1$ 列和第 $i + 1$ 列倒入（前提是这些列在网格范围内）。

然而，亚历山大不想引起洪水，因为那样所有的水最终都会静止不动。静止的水当然没有奔腾的水那么令人兴奋。因此，他希望你帮助编写一个程序，计算悬崖最底部一行中有多少列有水。

图 1：样例 1 和样例 2 中水流的示意图。红框标记了悬崖面的边缘。

输入格式

第一行包含两个整数 $R, C$ （$1 \le R, C \le 10^9$），表示组成悬崖的行数和列数。

第二行包含两个整数 $K, N$ （$1 \le K, N \le 10^5$），表示有水流入的列数和悬崖上突出岩石的数量。

接下来的 $K$ 行，第 $i$ 行包含一个数字 $V_i$ （$0 \le V_i \le C-1$），表示水从网格上方沿着第 $V_i$ 列向下流。保证所有的 $V_i$ 互不相同。

此后有 $N$ 行，其中每行 $i$ 包含两个整数 $A_i$ （$1 \le A_i \le R-1$）和 $B_i$ （$0 \le B_i \le C-1$），表示第 $i$ 个岩石所在的行和列。这些位置也是互不相同的。

输出格式

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

样例

输入样例 1

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

输出样例 1

3

输入样例 2

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

输出样例 2

1

输入样例 3

5 4
1 3
3
1 1
2 2
3 3

输出样例 3

1

子任务

您的解法将在若干个测试点结合上进行测试，每个测试点结合对应一定的分值。每个测试点结合包含若干个测试用例。要获得一个测试点结合的分数，您需要通过该测试点结合中的所有测试用例。