#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
bool v[70],d[70];
inline int read() {
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    int x=0;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
signed main(void) {
    int n,m,c,k;
    scanf("%d%d%d%d",&n,&m,&c,&k);
    for(int i=0;i<n;++i) {
        int tmp=read();
        int j=k-1;
        for(;j>=0;--j) v[j]|=(tmp>>j)&1;
    }
    for(int i=1;i<=m;++i) {
        int p=read(),q=read();
        if(!v[p]) d[p]=1;
    }
    int cnt=0;
    for(int i=0;i<k;++i) cnt+=d[i];
    if((k-cnt)^64) printf("%llu\n",(1ull<<(k-cnt))-n);
    else 
        if(n) printf("%llu",(int)(-n));
        else puts("18446744073709551616");
    return 0;
}