#include<bits/stdc++.h>
using namespace std;
struct ins{
	int noo;
	int bitt;
}s[1145140];
bool cmp(ins a,ins b)
{
	return a.noo>b.noo;
}

bool b[70],bb[70],xx[70][1000010];
int main()
{
	#define int unsigned long long
	//freopen("zoo3.in","r",stdin);
	//freopen("julian3.out","w",stdout);
	long long n,m,c,k;
	memset(b,0,sizeof(b));
	memset(bb,0,sizeof(bb)); 
	cin>>n>>m>>c>>k;
			if(n==0&&k==64)
		{
			return cout << "18446744073709551616", 0;
		}
	for(int i=1;i<=n;i++)
	{
		unsigned long long t;
		scanf("%lld",&t);
		for(int j=0;j<k;j++)
		{
			b[j]|=(t&1ull);
			t>>=1ull;
			bb[j]=b[j];
			if(t==0)break;
		}

		//for(int j=0;j<k+2;j++)cout<<setw(2)<<b[j];
		//cout<<endl;
	}
	
	long long p=0,last=-1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&s[i].bitt,&s[i].noo);//printf("%d %d\n",s[i].bitt,s[i].noo);
	}
	
		
	//for(int i=1;i<=m;i++)
	sort(s+1,s+m+1,cmp);
	//for(int i=1;i<=m;i++)printf("%d %d\n",s[i].bitt,s[i].noo);
	//return 0;
	for(int i=1;i<=m;i++)
	{
		if(s[i].noo!=last)
		{
			last=s[i].noo;
			p++;
			
		}
		xx[s[i].bitt][p]=1;
	}
	//return 0;
	/*
	for(int i=0;i<=k-1;i++)
	{
		for(int j=1;j<=p;j++)cout<<setw(2)<<xx[i][j];
		cout<<endl;	
	}*/
	
	for(int i=0;i<=k-1;i++)
	{
		if(b[i])
		{
			for(int j=0;j<=k-1;j++)
			{
				if(!bb[j])
				{
					bool f=1;
					for(int l=1;l<=p;l++)
					{
						if(xx[j][l]&&!xx[i][l])
						{
							f=0;break;
						}
					}
					bb[j]=f;
				}
			}
		}
		/*for(int j=0;j<k;j++)cout<<setw(2)<<bb[j];
		cout<<endl;*/
	}
	int kk=0;
	for(int i=0;i<k;i++)kk+=bb[i];
	unsigned long long result=(1<<kk)-n;
	cout<<result<<endl;
}