#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

#define MAX_N 1020

long long n, m, h, K, a, b, s[MAX_N], goal2[MAX_N];
vector<long long>x[MAX_N];
vector<long long> goal[MAX_N];
vector<long long> y[MAX_N][500][2];

long long amida[MAX_N][500][2];
long long amida2[MAX_N][MAX_N];

void _memset() {
	for (int i = 0; i < MAX_N; i++) {
		x[i].clear();
		goal[i].clear();
		for (int j = 0; j < MAX_N; j++) {
			y[i][j][0].clear();
			y[i][j][1].clear();
		}
	}
	memset(goal2, 0, sizeof(goal2));
	memset(amida, 0, sizeof(amida));
	memset(amida2, 0, sizeof(amida2));
	memset(s, 0, sizeof(s));
}

long long AMIDA2(long long P,long long H) {
	long long L = 0, M = 1145141919810LL, D = 0;
	while (true)
	{
		M = 1145141919810LL;
		D = amida2[P][H];

		if (x[P].size() > D) {
			M = x[P][D];
			L = 0;
		}

		D = amida2[P - 1][H];

		if (x[P - 1].size() > D) {
			if (x[P - 1][D] <= M) {
				M = x[P - 1][D];
				L = 1;
			}
		}

		if (M >= 1145141919) {
			goto E;
		}
		if (L == 0) { P++; H = M; }
		else { P--; H = M; }

	}
E:;
	return P;
}

void AMIDA() {

	for (int i = 1; i <= n; i++) {
		for (int g = 0; g < x[i].size(); g++) {
			amida[i][g][0] = AMIDA2(i, x[i][g] - 1);
			amida[i][g][1] = AMIDA2(i + 1, x[i][g] - 1);
		}
	}

}

long long search() {
	long long minx2 = 0, sum = 0;

	AMIDA();

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < x[i].size(); j++) {
			sum = 0;
			long long a1 = s[amida[i][j][0]];
			long long a2 = s[amida[i][j][1]];

			for (int k = 0; k < y[i][j][0].size(); k++) {
				if (y[i][j][0][k] <= K) {
					sum += a2 - a1;
				}
			}

			for (int k = 0; k < y[i][j][1].size(); k++) {
				if (y[i][j][1][k] <= K) {
					sum += a1 - a2;
				}
			}

			minx2 = min(minx2, sum);
		}
	}

	return minx2;
}

long long score() {

	long long minx = 0LL;

	//hajime.
	for (int i = 1; i <= K; i++)
	{
		long long P = i, H = 0, M = 1145141919810LL, L = 0, Q1 = 0, Q2 = 0;

		while (true)
		{
			M = 1145141919810LL;
			for (int j = 0; j < x[P].size(); j++)
			{
				if (x[P][j] > H) {
					Q1 = j;
					M = x[P][j];
					L = 0;
					break;
				}
			}

			for (int j = 0; j < x[P - 1].size(); j++) {
				if (x[P - 1][j] > H) {
					if (x[P - 1][j] <= M) {
						Q2 = j;
						M = x[P - 1][j];
						L = 1;
					}
					break;
				}
			}

			if (M >= 1145141919) {
				goto E;
			}
			if (L == 0) { y[P][Q1][0].push_back(i); P++; H = M; }
			else { y[P - 1][Q2][1].push_back(i); P--; H = M; }

		}
	E:;
		goal[P].push_back(i);
		goal2[i] = P;
	}

	for (int i = 1; i <= n; i++) {
		minx += s[i] * goal[i].size();
	}

	return minx + search();
}

void amidakuji() {
	int cnt;
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		for (int j = 0; j < MAX_N; j++) {
			if (x[i].size() != cnt) {
				if (x[i][cnt] == j) {
					cnt++;
				}
			}
			amida2[i][j] = cnt;
		}
	}
}

int main() {
	while (true) {
		_memset();
		cin >> n >> m >> h >> K;
		if (n == 0 && m == 0 && h == 0 && K == 0) { break; }
		for (int i = 1; i <= n; i++) {
			cin >> s[i];
		}
		for (int i = 0; i < m; i++) {
			cin >> a >> b;
			x[a].push_back(b);
		}
		for (int i = 0; i <= n; i++) {
			sort(x[i].begin(), x[i].end());
		}

		amidakuji();

		cout << score() << endl;
	}
	return 0;
}

Measured memory_bytes: 47152