#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 2e5 + 5;
int t, n, m, k, q, a[N], tree[4 * N], tag[4 * N], ans;
struct node{
	int l, r;
}p[N];
void pushup (int x){
	tree[x] = tree[(x << 1)] + tree[(x << 1) + 1];
	return ;
}
void addtag (int l, int r, int x, int val){
	tag[x] += val;
	tree[x] += (r - l + 1) * val;
	return ;
}
void pushdown (int l, int r, int x){
	if (tag[x] == 0) return ;
	int mid = l + r >> 1;
	addtag (l, mid, (x << 1), tag[x]);
	addtag (mid + 1, r, (x << 1) + 1, tag[x]);
	tag[x] = 0;
	return ; 
}
int query (int l, int r, int x, int y, int cur){
	if (r < x || l > y) return 0;
	if (x >= l && r <= y) return tree[cur];
	int mid = l + r >> 1;
	pushdown (l, r, cur);
	return query (l, mid, x, y, (cur << 1)) + query(mid + 1, r, x, y, (cur << 1) + 1);
}
void update (int l, int r, int x, int y, int cur, int val){
	if (r < x || l > y) return ;
	if (x >= l && r <= y){
		addtag(l, r, cur, val);
		return ;
	}
	int mid = l + r >> 1;
	pushdown (l, r, cur);
	update (l, mid, x, y, (cur << 1), val);
	update (mid + 1, r, x, y, (cur << 1) + 1, val);
	pushup(cur);
	return ;
}
bool check (int x){
	int tot = 0;
	for (int i = 1; i <= 4 * n; ++i) tag[i] = tree[i] = 0;
	for (int i = 1; i <= n; ++i){
		int pos = a[i] + query (1, n, i, i, 1) * q;
		if (pos >= x) continue;
		int tmp = 0;
		if (!((x - pos) % q)) tmp = (x - pos) / q;
		else tmp = ceil ((double)(x - pos) / q);
		tot += tmp;
		int lt = 1, rt = m, posl;
		while (lt <= rt){
			int mid = lt + rt >> 1;
			if (p[mid].l <= i){
				posl = mid;
				lt = mid + 1;
			}else rt = mid - 1;
		}
		update (1, n, p[posl].l, p[posl].r, 1, tmp * q);
	}
	return tot <= k;
}
bool cmp (node x, node y){
	return x.r < y.r;
}
signed main (){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> t;
	while (t --){
		ans = 0ll;
		cin >> n >> m >> k >> q;
		int l = 1e18, r = -1e18;
		for (int i = 1; i <= n; ++i){
			cin >> a[i];
			l = min (l, a[i]);
			r = max (r, a[i] + k * q);
		}
		for (int i = 1; i <= m; ++i) cin >> p[i].l >> p[i].r;
		sort (p + 1, p + m + 1, cmp);
		while (l <= r){
			int mid = l + r >> 1;
			if (check(mid)){
				ans = mid;
				l = mid + 1;
			}else r = mid - 1;
		}
		cout << ans << '\n';
	}
	return 0;
}