题目描述：

在一家电子制造工厂中，有一个专门存放电子元件的仓库。仓库管理员小李需要根据仓库中已存储的电子元件情况，按照《元件采购指南》来确定需要采购的零件种类，并将采购清单交给采购员小张。 在电子元件的世界里，总共有2^k 种不同的电子元件，这些元件被依次编号为0到2^k−1。目前，仓库里实际存储了其中的n种电子元件，对于这n种元件，第i种元件的编号记为ai ，且这些元件的编号ai两两互不相同。

《元件采购指南》中详细规定了m条关于零件采购的要求。对于第j条要求，其具体内容为：当仓库中存储的某种电子元件，其编号的二进制表示的第pj位（这里将元件编号的二进制表示看作一个k位的01串，其中第0位是最低位，第k−1位是最高位）为1时，就必须采购第qj种零件。需要注意的是，零件的种类一共有c种，并且这些零件从1到c进行编号，同时所有的qj也两两互不相同。

根据《元件采购指南》以及当前仓库存储的电子元件情况，仓库管理员小李会生成一个零件采购清单。该清单可以看作是一个c位的01串，当清单的第i位为1时，代表需要采购第i种零件；当第i位为0时，则表示不需要采购第i种零件。 有趣的是，从已采购的零件角度来看，仓库实际上可能还具备存储更多电子元件的条件。具体来说，对于当前未在仓库中存储的编号为x的电子元件，如果将它放入仓库进行存储后，零件采购清单不会发生任何改变，那么我们就认为仓库目前还能够存储编号为x的这种电子元件。 现在，采购员小张希望你能帮忙计算一下，按照现有的零件采购情况，仓库目前还能够存储多少种不同的电子元件呢？

输入格式：

输入数据的第一行包含四个以空格分隔的整数n、m、c、k。 其中n表示仓库中现有的电子元件数量，m表示《元件采购指南》中规定的要求数量，c表示零件的总种数，k表示电子元件编号的二进制表示所具有的位数。

第二行包含n个以空格分隔的整数，其中第i个整数表示ai，即当前仓库中第i种电子元件的编号。

接下来的m行，每行包含两个整数pi和qi，分别表示《元件采购指南》中的一条要求。

输出格式：

输出仅一行，包含一个整数，该整数表示按照当前情况，仓库还能够存储的电子元件的种类数量。

样例：

5 5 5 5
15 0 7 13 18 
1 5
4 3
0 1
2 2
3 4

27

提示

0≤n,m≤10^6，0≤k≤64，1≤c≤10^8。