#include<bits/stdc++.h>
#define re register int
#define ull unsigned long long 
using namespace std;
inline void read(int &x)
{
	x=0;
	int flag=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')	
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();		
	}
	x*=flag;
}
inline void uread(ull &x)
{
	x=(ull)0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')	
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();		
	}
}
const int N=1e6+5;
int n,m,c,k,p[N],q[N],cnt;
ull a[N];
ull tool,buy,all,fan,tmp,ans;
ull C[100][100];
inline void calc(int cnt)
{
	C[1][0]=1,C[1][1]=1;
	for(re i=2;i<=cnt+1;++i)
		for(re j=0;j<=i;++j)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
}
inline void print(ull x)
{
	if(x/10)
		print(x/10);
	putchar(x%10+'0');
}
int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	read(n),read(m),read(c),read(k);
	for(re i=1;i<=n;++i)
		uread(a[i]),all|=a[i];
	for(re i=1;i<=m;++i)
		read(p[i]),read(q[i]),tool|=(1<<p[i]);
	buy=tool&all;
	tmp=fan=tool^buy;
	while(tmp)
	{
		cnt+=(tmp&1);
		tmp>>=1;
	}
	calc(cnt);
	for(re i=1,ccnt=1;i<=cnt;++i,ccnt^=1)
	{
		ull tmp=C[cnt][i]*(1<<(k-i));
		ccnt?ans+=tmp:ans-=tmp;		
	}
	ull s=1<<k;
	ans=s-ans-(ull)n;
	print(ans);
	return 0;
}