#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
using namespace std;
inline char gt()
{
	static char buf[1<<21],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2) ? EOF:*p1++;
}
template <typename T>
inline void read(T &x)
{
	x=0;register char ch=gt();int w(0);
	while(!(ch>='0'&&ch<='9')) w|=ch=='-',ch=gt();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=gt();
	w?x=~(x-1):x;
}
template <typename T>
inline void out(T x)
{
	if(x<0) x=-x,putchar('-');
	int num(0);char s[30];
	while(x||!num) s[++num]=x%10+48,x/=10;
	while(num) putchar(s[num--]);
	putchar('\n');
}
typedef unsigned long long ull;
const int N=1e6+79;
ull n,m,c,k;//动物数 ，要求数，饲料数，最多位数 
ull a,state1,state2;//宠物编号 
ull ans;
ull x, y;
signed main()
{
//	read(n);read(m);read(c);read(k);
	cin>>n>>m>>c>>k;
	if(n==0&&m==0){
		if(k==64) return !printf("18446744073709551616");
		else return !(cout<<(1ull<<k));
	}
	rep(i,1,n)
	{
		cin>>a;
//		read(a);
		state1|=a; 
	}
	rep(j,1,m)
	{
		cin>>x>>y;
//		read(x);read(y);
		state2|=(1<<x);
	}
	ull cnt(0);
	rep(i,0,k-1)
	{
		ull t=1ull<<i;
		if(  (!(state1&t ) )&&(  (state2&t)   ) )
		 cnt++;
	}
	ull ans=(1ull<<(k-cnt))-n;
	cout<<ans;
//	out(ans);
	return 0;
}