#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, m, k, p, l = 1e18, r, tre[N], ar[N];
struct node
{
	int l, r;
}a[N];
bool cmp (node x, node y)
{
    if (x.l == y.l)
        return x.r < y.r;
    return x.l < y.l;
}
int lowbit(int x)
{
	return x & (-x);
}
void build(int res, int x)
{
	while(res <= n)
	{
		tre[res] += x;
		res += lowbit(res);
	}
}
int query(int x)
{
	int res = 0;
	while(x > 0)
	{
		res += tre[x];
		x -= lowbit(x);
	}
	return res;
}
inline bool check (int x)
{
    int cnt = 1, t = 0;
    for (int i = 1;i <= n; ++ i)
    {
    	int w = ar[p] + query(p);
        if (w >= x) continue;
        if (a[cnt].l < i && a[cnt].r < i)
        {
            while (a[cnt].l < i && a[cnt].r < i)
            {
                cnt = -~cnt;
                if (cnt == m && (a[cnt].l < i && a[cnt].r < i)) return 0;
            }
        }
        while (a[cnt].l <= i && a[cnt].r >= i)
        {
            build(a[cnt].l, p);
			build(a[cnt].r + 1, -p);
			++ t;
			if (t > k) return 0;
			w += p;
            if (w >= x) break;
            cnt = -~cnt;
            if ((a[cnt].l > i || a[cnt].r < i) && w < x)
            {
                return 0;
            }
        }
    }
    return 1;
}
void add ()
{
    int ans = 0;
    l = 1e18, r = 1;
	cin >> n >> m >> k >> p;
	for(int i = 1;i <= n; ++ i)
	{
		cin >> ar[i];
		l = min (l, ar[i]);
		r = max (r, ar[i]);
	}
    r += k * p;
	for (int i = 1;i <= m; ++ i)
	{
		cin >> a[i].l >> a[i].r;
	}
    sort (a + 1, a + m + 1, cmp);
    ans = l;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        memset (tre, 0, sizeof tre);
        if (check (mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
	cout << ans << "\n";
}
signed main()
{
	int _;
	cin >> _;
	while (_ --)
	{
		add();
	}
	return 0;
}