#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,m,k,c;
const int maxn=1e6+100;
/*鍒嗗埆琛ㄧず鍔ㄧ墿鍥腑鍔ㄧ墿
鏁伴噺銆併€婇ゲ鍏绘寚鍗椼€嬭姹傛暟銆侀ゲ鏂欑鏁颁笌鍔ㄧ墿缂栧彿鐨勪簩杩涘埗琛ㄧず浣嶆暟*/
ull a[maxn];//biao hao
set<int> s;
vector<int> nod[100];
ull work(ull a,ull b)
{//cout<<"s";
if(b==0) return 1;
	ull tmp=work(a,b/2);
	
	if(b%2==0) return  tmp*tmp;
		else return tmp*tmp*a;
}
int main(){

	freopen("zoo14.in","r",stdin);
	cin>>n>>m>>c>>k;
	
	ull tmp(0);
	for(int i=1;i<=n;i++)
		scanf("%llu",&a[i]),tmp|=a[i];
	//	cout<<tmp;
		for(int i=1;i<=m;i++)
		{
			ull x,y;
			scanf("%llu %llu",&x,&y);
			nod[x].push_back(y);
		//cout<<x<<" "<<y<<endl;
			if(tmp & ( 1<<x ) ) s.insert(y);
		}
	/*	set<int>::iterator it;
		for(it=s.begin();it!=s.end();it++)
		cout<<*it<<"bug ";*/
		ull cnt=0;
		for(int i=0;i<k;i++)
		{
			int ok=0;
			
			for(int j=0;j<nod[i].size();j++)
			if(s.find(nod[i][j])==s.end()) 
			{
				//cout<<nod[i][j]<<" ";
				ok=1;
				break;
			}
			
			if(ok==0) cnt++;
		}
				
			//	cout<<cnt;
	      if(cnt!=64)  cout<<work(2,cnt)-n;
	      else cout<<(1<<63)-n+(1<<63);
	
	//cout<<"bug";
	
/*	5 5 5 5
15 0 7 13 18 
1 5
4 3
0 1
2 2
3 4*/

	
	
	return 0;
}

用的是set和vector暴力搜索