#include <bits/stdc++.h>
#define rei register int
#define N 10000010
#define Log 64
using namespace std;
typedef unsigned long long ull;

ull n, m, c, k, a[N], used[N], b, x, y, bo[N], food[N], cnt, ans;

int main()
{
	//freopen("zoo3.in", "r", stdin);
	cin >> n >> m >> c >> k;
	for (rei i = 1; i <= n; i++)
	{
		cin >> a[i];
		ans |= a[i];
	}
	for (rei i = 1; i <= m; i++)
	{
		cin >> x >> y;
		if (((1ull << x) & ans) == 0) used[x] = 1;
	}
	for (rei i = 0; i <= Log; i++)
		if (used[i]) cnt++;
	cnt = k - cnt;
	if (!cnt)
	{
	    cout <<0 <<endl; return 0;
	}
	if (cnt == 64 && n == 0)
	{
		printf("18446744073709551616\n");
		return 0;
	}
	cout << (1ull << cnt) - n << endl;
	return 0;
}

wa 了 第18点