#include<bits/stdc++.h> #define N 1000005 usingnamespacestd; typedefunsignedlonglong ull;
template <typename T> inlinevoidread(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];
voidsolvebuy(){ for (int i = 1; i <= m; i++) { if ((S>>p[i])&1) buy[i] = 1; } } voidsolveans(){ 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; }
intmain(){ read(n); read(m); read(c); read(k); if (!n && !m && k == 64) { puts("18446744073709551616"); return0; } 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好像不太行 return0; }