**include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int t,n,m,k,a,A[N],cnt[N],tag[N];
vector<pair<int,int>>s;
bool check(int x){
    memset(cnt,0,sizeof(int)*(n+2));
    memset(tag,0,sizeof(int)*(n+2));
    int need=0,cur=0,res=0;
    for(int i=1;i<=n;i++){
        if(A[i]<x){
            int d=(x-A[i]+a-1)/a;
            cnt[i]=d;
        }
    }
    vector<vector<int>>c(n+2);
    for(int i=0;i<m;i++)c[s[i].first].push_back(i);
     for(int i=1;i<=n;i++){
        cur+=tag[i];
        cnt[i]-=cur;
        while(cnt[i]>0){
            int sel=-1;
            for(int j:c[i]){
                if(tag[s[j].second+1]==0){
                    sel=j;
                    break;
                }
            }
            if(sel==-1)return 0;
            int l=s[sel].first,r=s[sel].second;
            tag[l]+=1;
            tag[r+1]-=1;
            cur++;
            res++;
            if(res>k)return 0;
            cnt[i]-=1;
        }
    }
    return res<=k;
}
signed main(){
    cin>>t;
    while(t--){
        s.clear();
        cin>>n>>m>>k>>a;
        for(int i=1;i<=n;i++)cin>>A[i];
        for(int i=0;i<m;i++){
            int l,r;
            cin>>l>>r;
            s.push_back({l,r});
        }
        int l=1,r=2e13,ans=1;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}