#include <iostream>
#include <cstdio>
using namespace std;
long long n,m,c,k;
const int N=2000;
unsigned long long ans=1;
long long a[1000050];
bool lis[N],vis[N];
unsigned long long ki,li;

int main()
{
	//freopen("zoo.in","r",stdin);
	//freopen("zoo.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&m,&c,&k);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=m;++i) 
	{
		unsigned long long p,q;
		scanf("%llu%llu",&p,&q);
		if(!lis[p]) k--,lis[p]=1;
	}
	for(int i=1;i<=n;i++)
	{
		int u=a[i];
		int j=0;
		while(u)
		{
			if(u&1&&!vis[j]&&lis[j]!=0) vis[j]=1,k++;
			u>>=1;j++;
		}
	}
	for(int i=1;i<=k;i++) ans*=2;
	ans-=n;
	printf("%llu\n",ans);
	return 0;
}