#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M LLONG_MAX
pair<ll,ll> a[100000];
ll flg[100000][2];
int main(void){
	ll n,m,h,k,i,j,mi,s[1000],sp[1000],ss[1000],sum,p,pp;
	while(1){
		cin>>n>>m>>h>>k;
		if(n==0)break;
		for(i=0;i<n;i++) cin>>s[i],sp[i]=i;
	//	for(i=0;i<n;i++) cout<<s[i][0]<<' '<<s[i][1]<<endl;
		for(i=0;i<m;i++) cin>>a[i].second>>a[i].first;
		sort(a,a+m);
	//	for(i=0;i<m;i++) cout<<a[i].second<<' '<<a[i].first<<endl;
		for(i=0;i<m;i++){
			swap(sp[a[i].second-1],sp[a[i].second]);
			flg[i][0]=sp[a[i].second];
			flg[i][1]=sp[a[i].second-1];
		}
	//	for(i=0;i<m;i++) cout<<flg[i][0]<<' '<<flg[i][1]<<endl;
		for(i=0;i<n;i++) ss[sp[i]]=i;
	//	for(i=0;i<n;i++) cout<<s[i][0]<<endl;
		mi=0;
		for(i=0;i<k;i++) mi+=s[ss[i]];
		for(i=0;i<m;i++){
			p=flg[i][0]; pp=flg[i][1];
			swap(ss[p],ss[pp]);
			sum=0;
			for(j=0;j<k;j++){
				sum+=s[ss[j]];
	//			cout<<i<<' '<<s[ss[j]]<<endl;
			}
			mi=min(mi,sum);
			swap(ss[p],ss[pp]);
		}
		cout<<mi<<endl;
	}
	return 0;
}
