#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
int N,M,H,K;
int S[1000];
P ab[100000];
bool F[1000][1000];
int now[1000];
int point[1000];
int ans;
int main()
{
	while(true){
	scanf("%d%d%d%d",&N,&M,&H,&K);
	if(N==0)return 0;
	for(int i=0;i<N;i++)now[i]=i;
	for(int i=0;i<N;i++)scanf("%d",&S[i]);
	for(int i=0;i<M;i++){
		int A,B;
		scanf("%d%d",&A,&B);
		A--;
		ab[i].first=B;ab[i].second=A;
	}
	sort(ab,ab+M);
	for(int i=0;i<M;i++){
		F[now[ab[i].second]][now[ab[i].second+1]]=true;
		swap(now[ab[i].second],now[ab[i].second+1]);
	}
	for(int i=0;i<N;i++){
		point[now[i]]=S[i];
	}
	int cou=0;
	for(int i=0;i<K;i++)cou+=point[i];
	ans=cou;
	for(int i=0;i<N;i++){
		for(int j=i+1;j<N;j++){
			if(F[i][j]){
				if(j<K)continue;
				if(i>=K)continue;
				int cou1=cou;
				cou1+=point[j];cou1-=point[i];
				ans=min(ans,cou1);
			}
		}
	}
	printf("%d\n",ans);
	}
	return 0;
}