#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n,m,c,k;
ull a,A;
ll ans1,ans2;
int cnt;

int main()
{
	scanf("%d%d%d%d",&n,&m,&c,&k);
	for(int i=1;i<=n;i++)
	{
		ull t;
		scanf("%lld",&t);
		a|=t;
	}
	for(int i=1;i<=m;i++)
	{
		int p,q;
		scanf("%d%d",&p,&q);
		A|=(ull)1<<p;
	}
	a=(A^a)^((A^a)&a);
	A=1;
	for(int i=0;i<k;i++,A<<=1) 
		if(A&a) cnt++;
	ans2=1;
	for(int i=0;i<k-cnt;i++)
	{
		ans1*=2;
		ans2*=2;
		if(ans2>100000000000) ans1+=ans2/100000000000,ans2%=100000000000;
	}
	ans2-=n;
	if(ans2<0) ans2+=100000000000,ans1--;
	if(ans1<0)
	{
		puts("0");
		return 0;
	}
	if(ans1) printf("%lld",ans1);
	for(ll t=10000000000;ans1 && t>ans2 && t>1;t/=10) putchar('0');
	printf("%lld\n",ans2);
	return 0;
}

不知道为啥怎么都过不了