#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<cmath>

using namespace std;

typedef unsigned long long ll;
set<ll> st;
ll n,m,tt,ans,c,k,bb[1000001],aa[1000001];
bool vis[1000001],chk[1000001];

int main(){
	scanf("%llu%llu%llu%llu",&n,&m,&c,&k);
	for(ll i=1;i<=n;i++){
		ll x;
		scanf("%llu",&x);
		tt|=x;
	}
	ll t1=tt,pos=0;
	while(tt){
		chk[pos++]=tt&1;
		tt>>=1;
	}
	tt=k;
	for(ll i=1;i<=m;i++){
		scanf("%llu%llu",&aa[i],&bb[i]);
		if(!chk[aa[i]]){
			tt--;
			chk[aa[i]]=1;
		}
	}
	if(tt==64){
		if(n==0){
			printf("%.0lf",pow(2,64));
			return 0;
		}
		double tttt=pow(2,64)-(double)(n);
		printf("%.0lf",tttt);
		return 0;
	}
	ans=(1llu<<tt)-(n);
	printf("%llu",ans);
	return 0;
}