#include <iostream>
#include <algorithm>
#include <utility>
#include <cstring>
#include <vector>
#include <functional>
using namespace std;
#define INF 2000010000

pair<int,int> bou[100010],kae[100010];
int S[1010];int ar[1010],ra[1010];
int main(){
	int N,M,H,K,a,b,dai,sho,mim,res,cnt;
	while(true){
		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=1;i<=M;i++){
			cin>>a>>b;
			bou[i]=make_pair(b,a);
		}
		sort(bou+1,bou+M+1,greater<pair<int,int> >());
		for(int i=1;i<=N;i++) ar[i]=i;
		for(int i=1;i<=M;i++){
			kae[i]=make_pair(ar[bou[i].second],ar[bou[i].second+1]);
			swap(ar[bou[i].second],ar[bou[i].second+1]);
		}
		for(int i=1;i<=N;i++){
			ra[ar[i]]=i;
		}
		mim=0;
		for(int i=1;i<=M;i++){
			if(S[kae[i].first]>S[kae[i].second]){
				dai=ra[kae[i].first];sho=ra[kae[i].second];
			}
			else{
				dai=ra[kae[i].second];sho=ra[kae[i].first];
			}
			if(dai<=K&&sho>K){
				mim=max(mim,abs(S[kae[i].first]-S[kae[i].second]));
			}
		}
		cnt=0;
		for(int i=1;i<=K;i++){
			cnt+=S[ar[i]];
		}
		cout<<cnt-mim<<endl;
	}
	return 0;
}