#include<bits/stdc++.h>
#define int unsigned long long
#define N 1000005
using namespace std;

int n,m,c,k,all,cnt,a[N],p[N],q[N];

map<int,bool> M;

vector<int> v[105];

inline void read(int &s)
{
	s=0;
	char c=getchar();
	while(c<48||c>57)	c=getchar();
	while(c>47&&c<58)	s=s*10+c-48,c=getchar();
}

signed main()
{ 
//	freopen("1.in","r",stdin);
	read(n),read(m),read(c),read(k);
	for(int i=1;i<=n;i++)	read(a[i]),all=all|a[i];
	for(int i=1;i<=m;i++)
	{
		read(p[i]);
		read(q[i]);
		v[p[i]].push_back(q[i]);
		if((all&(1ull<<(p[i])))==0)
			M[q[i]]=1;
	}
	for(int i=1;i<=k;i++)
	{
		int flag=0;
		int l=v[i].size();
		for(int j=0;j<l;j++)
		{
			if(M[v[i][j]])
			{
				flag=1;
				break;
			}
		}
		cnt+=flag;
	}
	k=k-cnt;
	if(k==64)
	{
		if(!n)	cout<<"18446744073709551616";
		else
		{
			int ans=18446744073709551615ll-n+1;
			cout<<ans;
		}
	}
	printf("%lld",(1ull<<k)-n);
	return 0;
}