#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=200000+10,inf=1e9;
int n,m,k,dat,a[N],b[N],c[N],l,r,ret;
vector<int>nod[N];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il bool cmp(ri gd,ri gs){return gd>gs;}
il bool check(ri x)
{
    priority_queue<int>Q;ri as=0,tot=0;
    rp(i,1,n)b[i]=max(0,(x-a[i]+dat-1)/dat);memset(c,0,sizeof(c));
    rp(i,1,n)
    {
        tot+=c[i];ri sz=nod[i].size();rp(j,0,sz-1)Q.push(nod[i][j]);
        while(!Q.empty() && tot<b[i])
        {
            if(Q.top()<i)return false;++tot;--c[Q.top()+1];Q.pop();++as;
        }
        if(tot<b[i] || as>k)return false;
    }
    return true;
}

int main()
{
    // freopen("4064.in","r",stdin);freopen("4064.out","w",stdout);
    int T=read();
    while(T--)
    {
        n=read();m=read();k=read();dat=read();ret=l=0;rp(i,1,n)a[i]=read(),nod[i].clear();r=inf;
        rp(i,1,m){ri l=read();nod[l].push_back(read());}
        while(l<r){ri mid=(l+r)>>1;if(check(mid+1))l=mid+1;else r=mid;}
        printf("%d\n",l);
    }
    return 0; 
}