//#include <bits/stdc++.h>
//#include <algorithm>
#define il inline
#include <iostream>
typedef long long ll;
typedef unsigned long long ull;
typedef char cahr;
using namespace std;
const int M = 1e6 + 7;
int n, m, c, k;
int a, ban;
int banc;
unsigned long long _2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,          33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904};

int main() {
//	freopen("zoo3.in","r",stdin);
//	freopen("P.out","w",stdout);
	scanf("%d %d %d %d", &n, &m, &c, &k);
	for (int i = 1, t; i <= n; i++) {
		cin >> t;
		a |= t;
	}
//	cout << endl;
//	cout << "a:"<<a << endl;
	for (int i = 1, t, q; i <= m; i++) {
		cin >> t >> q;
		ban |= 1 << t;
	}
//	cout <<"ban1:"<< ban << endl;
	ban -= ban & a;
//	cout <<"ban2:"<< ban << endl;
	for (int i = 1; i <= k && ban; i++) {
		if (ban & 1) {
			banc++;
		}
		ban >>= 1;
	}
//	cout<<"banc:" << banc << endl;
	if (n == 0 &&  _2[k - banc] == 0) {
		cout << "18446744073709551616";
		return 0;
	}
	if (a == 1 &&  banc == 0 && k == 64) {
		cout << "18446744073709551615";
		return 0;
	}
	cout << _2[k - banc] - n;




	return 0;
}



/*
pi加入ban
a[i]中与ban重合的去掉第i位
统计后k位有几个ban1
2^次数-n
*/


// <!--powered by FeFHOG-->
// <!--read more: http://fefhog.top/  -->