#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string.h>
using namespace std;
#define N 1000
#define M 100000
#define S second
#define F first
#define MP(i, j) make_pair((i), (j))
#define INF 1e9
typedef pair<int, int> P;

vector<int> vec[N + 1][2], vec2, vec3;
P yoko[M];
int s[N + 1];
int main() {
	int n, m, h, k;
	while (cin >> n >> m >> h >> k && n && m && h && k) {
		int ans = INF, sum = 0;
		memset(s, 0, sizeof s);
		memset(yoko, 0, sizeof yoko);
		vec2.clear(); vec3.clear();
		for (int i = 0; i < n; i++) {
			scanf("%d", s + i);
			vec[i][0].clear();
			vec[i][1].clear();
		}
		for (int i = 0; i < m; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			yoko[i] = MP(b, a);
		}
		sort(yoko, yoko + m);
		for (int i = 0; i < n; i++) {
			vec[i][0].push_back(i);
		}
		for (int i = 0; i < m; i++) {
			int a = yoko[i].S;
			a--;
			int sz = vec[a][1].size();
			for (int j = 0; j < vec[a + 1][1].size(); j++) {
				vec[a][1].push_back(vec[a + 1][1][j]);
			};
			vec[a + 1][1].clear();

			for (int j = 0; j < sz; j++) {
				vec[a + 1][1].push_back(vec[a][1][j]);
			}
			vec[a][1].erase(vec[a][1].begin(), vec[a][1].begin() + sz);
			for (int j = 0; j < vec[a + 1][0].size(); j++) {
				vec[a][0].push_back(vec[a + 1][0][j]);
				vec[a + 1][1].push_back(vec[a + 1][0][j]);
			}
			vec[a + 1][0].erase(vec[a + 1][0].begin(), vec[a + 1][0].end());
			for (int j = 0; j < 1; j++) {
				vec[a + 1][0].push_back(vec[a][0][j]);
				vec[a][1].push_back(vec[a][0][j]);
			}
			if (vec[a][0].size())
				vec[a][0].erase(vec[a][0].begin(), vec[a][0].begin() + 1);
		}
		for (int i = 0; i < n; i++) {
			if (k >= vec[i][0][0] + 1) {
				sum += s[i];
				vec2.push_back(i);
			}
			else {
				vec3.push_back(i);
			}
			sort(vec[i][1].begin(), vec[i][1].end());
		}
		for (int i = 0; i < vec2.size(); i++) {
			for (int j = 0; j < vec3.size(); j++) {
				if (s[vec2[i]] > s[vec3[j]]) {
					if (binary_search(vec[vec3[j]][1].begin(), vec[vec3[j]][1].end(), vec[vec2[i]][0][0])) {
						ans = min(ans, sum - s[vec2[i]] + s[vec3[j]]);
					}
				}
			}
		}
		ans = min(ans, sum);
		cout << ans << endl;
	}
}