#include<bits/stdc++.h>
using namespace std;
inline void read(unsigned long long &x) {
	x = 0;
	register char c = getchar();
	while(c > '9' || c < '0')
		c = getchar();
	do {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	} while(c >= '0' && c <= '9');
}
int m,c,k,t;
unsigned long long animal,vis,n,ans,a,p,q;
int main() {
	cin >> n >> m >> c >> k;
	for(int i = 1; i <= n; ++i) {
		read(a);
		animal |= a;
	}
	for(int i = 1; i <= m; ++i) {
		read(p);
		read(q);
		if(!(animal & (1ull << p)))
			vis |= (1ull << p);
	}
	for(int i = 63; i >= 0; --i)
		if((1ull << i) <= vis) {
			++t;
			vis -= (1ull << i);
		}
	if(k == 64 && !t && !n)
		cout << "18446744073709551616";
	else {
		if(k == 64 && !t)
			ans = (1ull << (k - 1)) - n + (1ull << (k - 1));
		else ans = (1ull << (k - t)) - n;
		cout << ans;
	}
	return 0;
}