#include<iostream>
using namespace std;
const int MAXK = 64 + 8;
int n, m, c, k;
bool need[MAXK], cant[MAXK];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> c >> k;
	for(int i = 1; i <= n; i ++)
	{
		unsigned long long a;
		cin >> a;
		for(int j = 0; j < k; j ++)
			need[j] |= (a >> j) & 1;
	}
	for(int i = 1, p, q; i <= m; i ++)
	{
		cin >> p >> q;
		if(need[p] == 0)
			cant[p] = 1;
	}
	int cnt = 0;
	for(int i = 0; i < k; i ++)
		if(cant[i])
			cnt ++;
	if(k - cnt == 64)
	{
		if(n == 0)
        	cout << "18446744073709551616";
        else
        	cout << 18446744073709551615ull - n - 1;
	}
	else
		cout << (1ull << (k - cnt)) - n;
	return 0;
}