#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x = 0 ,f = 1;
	char ch = getchar();
	while('0' > ch || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
const int N = 2e5 + 5;
int T ,n ,m ,k ,a ,A[N] ,c[N];
struct stu {
	int Left ,Right;
	bool operator <(const stu &a)const {
		if(Left != a.Left) return Left < a.Left;
		else return Right < a.Right;
	}
}t[N];
int lowbit(int x) {
	return x & (-x);
}
void updata(int x,int a) {
	for(int i = x;i <= n;i += lowbit(i)) {
		c[i] += a;
	}
	return ;
}
int query(int x) {
	int sum = 0;
	for(int i = x;i > 0;i -= lowbit(i)) {
		sum += c[i];
	}
	return sum;
}
priority_queue<int>que;
bool check(int x) {
	while(!que.empty())que.pop();
	memset(c ,0 ,sizeof(c));
	int tmpt = 0;
	for(int i = 1 ,l = 1;i <= n;++ i) {
		int tmp = A[i] + query(i);
		if(tmp < x) {
			while(t[l].Left <= i && l <= m) {
				que.push(t[l].Right);
				++ l;
			}
			int tx = (x - tmp + a - 1) / a;
			tmpt += tx;
			if(tmp > k)return false;
			for(int j = 1;j <= tx;++ j) {
				if(que.empty() || que.top() < i)return false;
				updata(i ,a);
				updata(que.top() + 1 ,-a);
				que.pop();
			}
		}
	}
	return (tmpt <= k);
}
signed main() {
	T = read();
	while(T --) {
		memset(A ,0 ,sizeof(A));
		n = read(); m = read(); k = read(); a = read();
		for(int i = 1;i <= n;++ i) A[i] = read();
		for(int j = 1;j <= m;++ j) {
			t[j].Left = read(); t[j].Right = read();
		}
		sort(t + 1 ,t + m + 1);
		int l = 1 ,r = 2e8 + 5;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if(check(mid)) {
				l = mid;
			}
			else r = mid - 1;
		}
		cout << l << '\n';
	}
	return 0;
}