#include<iostream>
#include<cmath>
#include<map>
#define ull unsigned long long
using namespace std;
int n,m,k,cnt;
map<int,bool>mk;
ull c,x,wei;
int main(){
	scanf("%d%d%llu%d",&n,&m,&c,&k);
	int p,q;
	for(int i=1;i<=n;i++){
		scanf("%llu",&x);
		wei|=x;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&p,&q);
		if((wei>>p&1)||mk[q]){
			mk[q]=true;
			cnt+=1;
		}
	}
	ull ans=(1llu<<(k-m+cnt))-n;
	cout<<max(0llu,ans);
	return 0;	
}