#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,c,k,lis,in,bit;
int main(){
	cin>>n>>m>>c>>k;
	for(int i=1;i<=n;i++){
		cin>>in;
		lis|=in;
	}
	unsigned long long fre=0,res=0;
	for(int i=1;i<=m;i++){
		cin>>bit>>in;
		if(!((1<<bit)&lis)) res|=(1<<bit);
	}
	int num=0;
	while(res){
		num+=(res&1)?1:0;
		res>>=1;
	}
	if(k-num==64){
		if(n) cout<<(unsigned long long)-n;
		else cout<<"18446744073709551616";
	}
	else cout<<(unsigned long long)(1<<(k-num))-n;
	return 0;
}