#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull n,m,c,k;
ull a[1000005];
ull p[1000005];
ull mm[1000005];
ull read(){
ull x=0,f=1;
char ch;
ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
ull ans=0,temp1,temp2;
int main(){
memset(p,-1,sizeof(p));
n=read(),m=read(),c=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++){
temp1=temp2=0;
temp1=read(),temp2=read();
p[temp2]=temp1;//temp2为饲料种类,temp1为二进制位数
}
for(int i=1;i<=n;i++){//a[i]为动物
for(int j=1;j<=c;j++){
if((a[i]>>p[j])&&1==1){
mm[p[j]]++;
// if(mm[p[j]]==1){
// ans++;
// }
}
}
}
for(int i=0;i<k;i++){
ull ssr=0;
for(int j=1;j<=c;j++){
if(p[j]==i) ssr++;
}
if(ssr!=0&&mm[i]==0){
k--;
}
}
cout<<pow(2,k)-n;
return 0;
}