#include <iostream>
#include <cstring>
#include<set>
unsigned long long pow(int a,int b){
	return 1<<b;
}
using namespace std;
bool f[70];
set<unsigned long long int> s;
long long int sum=0;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	unsigned long long int n,m,c,k;
	cin>>n>>m>>c>>k;
	unsigned long long a[n],b[m][2];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		unsigned long long tmp=a[i];
		int s1=0;
		while(tmp){
			if(tmp&1){
				f[s1]=1;
			}
			tmp>>=1;
			s1++;
		}
	}
	for(unsigned int i=0;i<m;i++){
		cin>>b[i][0]>>b[i][1];
		if(f[b[i][0]]){
			s.insert(b[i][1]);
		}
	}
	for(unsigned int i=0;i<m;i++){
		if(!*s.find(b[i][1])){
			s.insert(b[i][1]);
			sum++;
		}
	}
	if(sum==0){
		cout<<pow(2,k)-n;
		return 0;
	}
	cout<<pow(2,k-sum)-n;
	return 0;
}