#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*) array, (T*) (array + N), val);
}
pii Dir [] = {
	{ 0, 1 },{ -1 ,1 },{ -1, 0 },
	{ -1 ,-1 },{ 0,-1 },{ 1 ,-1 },
	{ 1,0 },{ 1 ,1 }
};
signed main() {
	int n, m, h, k;

	while (scanf("%d %d %d %d", &n, &m, &h, &k)) {
		if (!n && !m && !h && !k)
			break;
		vector<vector<pair<int, pii>>> bar(n);
		vector<int> last(n);
		REP(i, n) {
			int a;
			scanf("%d", &a);
			last[i] = a;
			bar[i].push_back({ INT_MAX,{ i,-1 } });
		}
		vector<int> ax;
		REP(i, m) {
			int a, b;
			scanf("%d %d", &a, &b);
			a--;
			bar[a].push_back({ b,{ -1,a + 1 } });
			bar[a + 1].push_back({ b,{ -1,a } });
			ax.push_back(b);
		}
		ax.push_back(INT_MAX);
		REP(i, n) {
			bar[i].push_back({ 0,{-1, -1} });
			sort(ALL(bar[i]), greater<pair<int, pii>>());
		}
		sort(ALL(ax), greater<int>());
		ax.erase(unique(ALL(ax)), ax.end());
		REP(i, ax.size()) {
			REP(j, n) {
				auto itr = lower_bound(ALL(bar[j]), MP(ax[i], MP(INT_MAX, INT_MAX)), greater<pair<int, pii>>());
				if (itr->first == ax[i]) {
					auto nitr = itr;
					nitr++;
					if (nitr->second.second == -1) {
						nitr->second.first = itr->second.first;
					}
					else {
						auto neitr = lower_bound(ALL(bar[nitr->second.second]), MP(nitr->first, MP(INT_MAX, INT_MAX)), greater<pair<int, pii>>());
						neitr->second.first = itr->second.first;
					}
				}
			}
		}
		int sum = 0;

		map<int, int> lst;
		REP(i, n) {
			if (i < k)
				sum += last[bar[i][bar[i].size() - 1].second.first];
			lst[bar[i][bar[i].size() - 1].second.first] = i;
		}
		int ans = sum;
		REP(i, n - 1) {
			for (auto itr : bar[i]) {
				if (lst[itr.second.first] < k) {
					if (itr.second.second == i + 1) {
						auto itrt = lower_bound(ALL(bar[i + 1]), MP(itr.first, MP(INT_MAX, INT_MAX)), greater<pair<int, pii>>());
						if (lst[itrt->second.first] >= k) {
							ans = min(ans, sum + last[itrt->second.first] - last[itr.second.first]);
						}
					}
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 6668