#include <bits/stdc++.h>
#define int unsigned long long

using namespace std;
const int N = 1000;
const int M = 1e8 + 9;

bool flag[M];
int n,m,k,c;
int pan;
//
//inline void write(int x)
//{
//    if(x<0){
//    	putchar('-');
//		x=-x;
//	}
//    if(x>9) 
//		write(x/10);
//    putchar(x%10+'0');
//}
//
//inline int read()
//{
//	int s=0,f=1;
//	char ch=getchar();
//	while(ch<'0'||ch>'9'){
//		if(ch=='-')
//			f=-1;
//		ch=getchar();
//	}
//	while(ch>='0'&&ch<='9'){
//		s=s*10+ch-'0';
//		ch=getchar();
//	}
//	return s*f;
//}
vector<int>f[N];

bool vis[N];

signed main(){
	cin >> n >> m >> c >> k;
//	n=read(),m=read(),c=read(),k=read();
	for(int i = 1;i <= n;i ++){
		int a;
		cin >> a;
//		a=read();
		pan = pan | a;
	}
	for(int i = 1;i <= m;i ++){
		int a,b;
//		a=read(),b=read();
		cin >> a >> b;
		f[a].push_back(b);
	}
	
	int g = pan;
	
	for(int i = 0;i < 64;i ++){
		int a = (pan & 1);
		pan = (pan >> 1);
		
		if(a){
			for(int j = 0;j < f[i].size();j ++){
				flag[f[i][j]] = true;
			}
		}		
	}
	
	int ans = (1 << k);
	ans -= n;
	 
	int wei = k - 1;
	
	for(int i = 0;i < 64;i ++){
		for(int j = 0;j < f[i].size();j ++){
			if(flag[f[i][j]] == false){
				if(wei >= 0) {
					ans -= (1 << wei);
					wei--;
				} 				
				break;
			}
		}
	}
	
	cout << ans << endl;
	
}