#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000005
#define ll long long
using namespace std;

ll n,m,k,c,x,y;
bool flag,pd[65];
ll a[N];

int read()
{
	int x=0; bool flag=1; char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')flag=0;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return flag?x:-x;
}

string chen(string s, int k)
{
	int t,g,cnt=0;
	string ans;
	char c[10005];
	for(int i=s.size()-1; i>=0; i--)
	{
		t=(s[i]-48)*k+g;
		g=t/10;
		t%=10;
		c[++cnt]=char(t+48);
	}
	if(g)c[++cnt]=g+48;
	for(int i=1; i<=cnt; i++)ans=c[i]+ans;
//	cout<<endl;
	return ans;
	
}

string jian(string s1, string s2)
{
	while(s1.size()<s2.size())s1="0"+s1;
	while(s1.size()>s2.size())s2="0"+s2; 
	string t="";
	int c,g=0;
	for(int i=s1.size()-1; i>=0; i--)
	{
		c=s1[i]-s2[i]-g;
		if(c<0)
		{
			g=1;
			c+=10;
		}else g=0;
		t=char(c+48)+t;
	}
	return t;
}

string s="2";
string n1;

string stri(int n)
{
	int c;
	string s;
	while(n>0)
	{
		c=n%10;
		s=char(c+48)+s;
		n/=10;
	}
	return s;
}

int main()
{
//	freopen("zoo.in","r",stdin);
//	freopen("zoo.out","w",stdout);
	n=read(); m=read(); c=read();k=read();
	for(int i=1; i<=n; i++)a[i]=read();
	sort(a+1,a+1+n);
	for(int i=1; i<=m; i++)
	{
		flag=0;
		x=read(); y=read();
		if(pd[x])flag=1;
		for(int i=n; i>=1; i--)
		{
			if(flag==1)break;
			if(a[i]<(1<<x))break;
			else if((a[i]>>x)&1)flag=1;
		} 
		if(flag==false)
		{k--;pd[x]=1;}
//		cout<<k<<endl;
	}
	if(k<30)cout<<(1<<k)-n;
	else{
		n1=stri(n);
		for(int i=2; i<k; i++)s=chen(s,2);
		cout<<jian(s,n1);
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}