动物园[CSP2020]

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef unsigned long long ull;

template <typename T>
inline void read(T &num) {
	T x = 0; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar());
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	num = x; 
}

int n, m, c, k, p[N];
ull a[N], S, ans, fst;
bool buy[N], ok[N];

void solvebuy() {
	for (int i = 1; i <= m; i++) {
		if ((S>>p[i])&1) buy[i] = 1;
	}
}
void solveans() {
	for (int i = 0; i < k; i++) ok[i] = 1;
	for (int i = 1; i <= m; i++) {
		if (!buy[i]) ok[p[i]] = 0;
	}
	int cnt = 0;
	for (int i = 0; i < k; i++) if (ok[i]) cnt++;
	if (cnt == 64) {
		ans = (1ull << 63) - n + (1ull << 63);
	} else ans = (1ull << cnt) - n;
} 

int main() {
	read(n); read(m); read(c); read(k);
	if (!n && !m && k == 64) {
		puts("18446744073709551616");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		read(a[i]); S |= a[i];
	}
	for (int i = 1; i <= m; i++) {
		read(p[i]); read(fst);
	}
	solvebuy();
	solveans();
	cout << ans << endl; //%lld好像不太行 
	return 0;
}