#include<bits/stdc++.h>
#include<bitset>
using namespace std;
unsigned long long flag;
int n,m,c,k,a[64],cnt;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>c>>k;
	for(int i=1;i<=n;++i){
        unsigned long long x;
		cin>>x;
		flag|=x;
	}
	for(int i=1,p,q;i<=m;++i){
		cin>>p>>q;
		if(!((1<<p)&flag)) a[p]=1;
	}
	for(int i=0;i<=63;++i) if(a[i]) ++cnt;
	if(k==64&&cnt==0){
		if(n) cout<<(unsigned long long)(-n);
		else cout<<"18446744073709551616";
	}
	else cout<<(1ull<<(k-cnt))-n;
}