#include<bits/stdc++.h>
using namespace std;
unsigned long long n, m, c, k, a[1000005], i, j, sum, t, p, flag[100000005], kind;
int main()
{
	freopen("P7076_14.in","r",stdin);
	freopen("14.out","w",stdout);
	cin>>n>>m>>c>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sum=sum|a[i];
	}
	for(i=1;i<=m;i++)
	{
		cin>>t>>p;
		if(!(sum&(1<<t))&&flag[t]==0){
			flag[t]=1;
			kind++;
		}
	}
	cout<<(unsigned long long)(pow(2,k-kind)-n);
 	return 0;
}