#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull n,m,c,k;
ull a[1000005];
ull p[1000005];
ull mm[1000005]; 
ull read(){
	ull x=0,f=1;
	char ch;
	ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
ull ans=0,temp1,temp2;
int main(){
	memset(p,-1,sizeof(p));
	n=read(),m=read(),c=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++){
		temp1=temp2=0;
		temp1=read(),temp2=read();
		p[temp2]=temp1;//temp2为饲料种类，temp1为二进制位数 
	}
	for(int i=1;i<=n;i++){//a[i]为动物 
		for(int j=1;j<=c;j++){
			if((a[i]>>p[j])&&1==1){
				mm[p[j]]++;
			//	if(mm[p[j]]==1){
			//		ans++;
			//	}
			}
		}
	} 
	for(int i=0;i<k;i++){
		ull ssr=0;
		for(int j=1;j<=c;j++){
			if(p[j]==i) ssr++;
		}
		if(ssr!=0&&mm[i]==0){
			k--;
		}
	}
	
	cout<<pow(2,k)-n;
	return 0;
}