#include<iostream>
#include<algorithm>
#include<cmath>

#define ull unsigned long long 


using namespace std;

const int N = 1e6 + 10;

ull n, m, c, k, a, x, s, cnt, ans = 1;
bool v[N];

inline ull read()
{
	ull x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-')f = -1;
		ch =getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return f * x;
}

struct node
{
	ull p, q;
}f[N]; 

bool cmp(node a, node b)
{
	return a.p < b.p;
}

int main()
{
	n = read();
	m = read();
	c = read();
	k = read();
	for(int i = 1; i <= n; i ++ )
	{
		scanf("%llu", &a);
		x |= a;
	}
	for(int i = 1; i <= m; i ++ )
	{
		f[i].p = read();
		f[i].q = read();
	}
	sort(f + 1, f + m + 1, cmp);
	for(int i = 0; i < k; i ++ )
	{
		if((x >> i) & 1)
		{
			for(int j = 1; j <= m; j ++ )
			{
				if(f[j].p == i)
				{
					v[f[j].q] = 1;
				}
				if(f[j].p > i)break;
			}
		}
	}
	for(int i = 1; i <= m; i ++ )
	{
		if(v[i])
		{
			for(int j = 1; j <= m; j ++ )
			{
				if(f[j].q == i)
				{
					x |= (1 << f[j].p);
				}
				if(f[j].q > i)break;
			}
		}
	}
	while(x)
	{
		if(x & 1)ans <<= 1;
		x >>= 1;
	}
	printf("%llu", ans - n);
	return 0;
}