#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
ull n,m,c,k;
const int N=1000005;
ull a,animal;
int food[70];
void init() {
//	freopen("zoo.in","r",stdin);
//	freopen("zoo.out","w",stdout);
	scanf("%llu%llu%llu%llu",&n,&m,&c,&k);
	for(int i=1; i<=n; i++) {
		scanf("%llu",&a);
		animal|=a;
	}
	for(int i=1; i<=m; i++) {
		int p,q;
		scanf("%d%d",&p,&q);
		if(!food[p]) food[p]=1;
	}
}
ull pow(ull x) {
	ull res=1;
	for(ull i=1; i<=x; i++) res*=2;
	return res;
}
int main() {
	init();
	ull t=k;
	for(int i=0; i<k; i++) {
		int b1=animal&(1<<i),b2=food[i];
		if(b1==0&&b2!=0) t--;
	}
	ull ans;
	if(t<64) ans=pow(t)-n;
	else {
		ans=pow(63);
		ans--,ans<<=1,ans-=n,ans+=2;
	}
	if(k==64&&n==0&&m==0) {
//		ull tmp=pow(63);
//		tmp--,tmp<<=1,tmp++;
//		ull pp=tmp%10;
//		tmp/=10;
//		printf("%llu%llu",tmp,pp);
		printf("18446744073709551616");
	}
	else printf("%llu",ans);
	return 0;
}

特判了还只有70，，暴毙