#include <iostream>
#include <cmath>
int n, m, c, k;
bool avail[65], rm[65];
using namespace std;
bool needfood(int x, int p){
	return (x >> p) & 1;
}
int main(){
	cin >> n >> m >> c >> k;
	for(int i = 0; i < n; i++){
		unsigned long long tmp;
		cin >> tmp;
		for(int j = k-1; j >=0; j--) avail[j] |= needfood(tmp, j);
	}
	int t=k;
	for(int i = 0; i < m; i++){
		int p, q;
		cin >> p >> q;
		if(!avail[p]) rm[p]=true;
	}
	for(int i = 0; i <k; i++) if(rm[i]) t--;
	if(t==64){
		if(n==0) cout << "18446744073709551616" << endl;
		else cout << 1ull * (-n)<< endl;	
	} 
	else cout << (1ull<<t) - n << endl;
	return 0;
}