#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<functional>
#include<map>
#define P pair<int,int>
using namespace std;

P e[100000];
int main() {
	int a, b, c, d;
	while (cin >> a >> b >> c >> d, a | b || c || d) {
		int f[1000], j[1000], sum = 0;
		for (int g = 0; g < a; g++)f[g] = g;
		for (int g = 0; g < a; g++)scanf("%d", &j[g]);
		for (int g = 0; g < b; g++) {
			int h, i; scanf("%d%d", &h, &i);
			h--; e[g] = P(i, h);
		}
		sort(e, e + b);
		for (int g = 0; g < b; g++) {
			swap(f[e[g].second], f[e[g].second + 1]);
		}
		int MAX = 0, k[1000];
		for (int l = 0; l < a; l++) { k[l] = l; if (f[l] < d)sum += j[l]; }
		for (int g = b - 1; g >= 0; g--) {
			if (f[k[e[g].second]] < d) {
				if (f[k[e[g].second + 1]] >= d) {
					MAX = max(MAX, j[k[e[g].second]] - j[k[e[g].second+1]]);
				}
			}
			else {
				if (f[k[e[g].second + 1]] < d) {
					MAX = max(MAX, j[k[e[g].second+1]] - j[k[e[g].second]]);
				}
			}
			swap(k[e[g].second], k[e[g].second + 1]);
		}
		cout << sum - MAX << endl;
	}
}