#include <iostream>
#include <bitset>
#define LL unsigned long long
using namespace std;
LL n, m, c, k;
LL a[1000010];
LL cz[1000010][2];
bitset<10001>b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    b.reset();
    cin >> n >> m >> c >> k;
    // if(n==0&&m==0&&k==64)
	// {
        // printf("18446744073709551616");
        // return 0;
    // }
    for (register int i = 1; i <= n; i++)
        cin >> a[i];
    // get ith number use (x>>i)&1
    for (register int i = 1; i <= m; i++)
        cin >> cz[i][0] >> cz[i][1];
    int bittot = 0;
    for (register int i = 1; i <= n; i++)
    {
    	bittot |= a[i];
    }
    for (register int i = 1; i <= m; i++)
    {
    	if ((bittot >> cz[i][0]) & 1)
    	{
    		b[cz[i][0]] = 1;
    	}
    }
    int cnt = 0;
    for (register unsigned int i = 1; i <= m; i++)
    {
    	if (!(b[cz[i][0]]))
    		cnt++;
    }
    cout << (1ull << (k - cnt)) - n << endl;
    return 0;
}