题目描述

某大型生态园区饲养了多种动物。园区管理员小王根据已饲养动物的编号，按照《饲养规范》确定需要采购的饲料种类，并将采购清单交给后勤人员小李。

具体来说，动物世界共有 $2^k$ 种不同动物，编号为 $0 \sim 2^k - 1$。园区目前饲养了其中 $n$ 种，第 $i$ 种动物编号为 $a_i$。

《饲养规范》包含 $m$ 条规则，第 $j$ 条规则为：若园区中饲养的某种动物编号的二进制表示第 $p_j$ 位为 $1$，则必须采购第 $q_j$ 种饲料。饲料共 $c$ 种，编号 $1 \sim c$。动物编号的二进制表示视为 $k$ 位串，第 $0$ 位为最低位，第 $k-1$ 位为最高位。

管理员小王据此制定饲料采购清单：清单为一个 $c$ 位 $01$ 串，第 $i$ 位为 $1$ 表示需采购第 $i$ 种饲料，为 $0$ 表示不需要。

实际上，根据已有饲料，园区可能还能饲养更多动物。具体地，若将某种当前未饲养的编号为 $x$ 的动物加入后，采购清单不变，则认为该动物可以被饲养。

请计算园区目前还能饲养多少种动物。

输入格式

第一行包含四个以空格分隔的整数 $n, m, c, k$，分别表示已饲养动物数、规范规则数、饲料种类数与编号二进制位数。

第二行 $n$ 个以空格分隔的整数，第 $i$ 个整数为 $a_i$。

接下来 $m$ 行，每行两个整数 $p_i, q_i$ 表示一条规则。

数据保证所有 $a_i$ 互不相同，所有 $q_i$ 互不相同。

输出格式

仅一行一个整数，表示答案。

样例

3 3 5 4
1 4 6
0 3
2 4
2 5

13

2 2 4 3
1 2
1 3
2 4

2

提示

样例 1 解释

园区饲养编号 $1, 4, 6$ 的三种动物，规则共三条：

1. 若某动物编号第 $0$ 位为 $1$，则需采购第 $3$ 种饲料。
2. 若某动物编号第 $2$ 位为 $1$，则需采购第 $4$ 种饲料。
3. 若某动物编号第 $2$ 位为 $1$，则需采购第 $5$ 种饲料。

饲料采购情况：编号 $1$ 的第 $0$ 位为 $1$，需采购第 $3$ 种；编号 $4, 6$ 的第 $2$ 位为 $1$，需采购第 $4, 5$ 种。

加入编号 $0, 2, 3, 5, 7, 8, \ldots, 15$ 中任一动物后清单不变，故答案为 $13$。

【数据范围】

对于 $20 \%$ 的数据，$k \le n \le 5$，$m \le 10$，$c \le 10$，所有 $p_i$ 互不相同。

对于 $40 \%$ 的数据，$n \le 15$，$k \le 20$，$m \le 20$，$c \le 20$。

对于 $60 \%$ 的数据，$n \le 30$，$k \le 30$，$m \le 1000$。

对于 $100 \%$ 的数据，$0 \le n, m \le 10^6$，$0 \le k \le 64$，$1 \le c \le 10^8$。