#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,c,k,p,q,a[1000010];
unsigned long long b=0,ans=1;
int main(){
	//freopen("zoo.in","r",stdin);
	//freopen("zoo.out","w",stdout);
	cin>>n>>m>>c>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>p>>q;
		b|=1<<p;
	}b=~b;
	for(int i=0;i<n;i++)b|=a[i];
	unsigned long long cnt=0,bb=b;
	for(int i=0;i<k;i++){
		if(bb&1)cnt++;
		bb=bb>>1;
	}
	if(cnt==64){
		cout<<(18446744073709551615-n)+1;
		return 0;
	}
	for(int i=0;i<k;i++){
		ans*=(b&1?2:1);
		b=b>>1;
	}
	cout<<ans-n;	
	return 0;
}