#include <cstring>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
#include <utility>
#include <cstring>
#include <map>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(int i=0;i<(n);i++)
#define mp(a,b) make_pair((a),(b))

typedef long long int lli;
typedef pair<int,int> P;

const int INF=100000000;
const long long int INF_=1000000000000000000;

int N,M,H,K; //縦棒の本数、横棒の本数、縦棒の長さ、選ぶ縦棒の本数

bool isIn(int x){
	return 0<=x&&x<K;
}

int pre(const vector<int> &s,vector<int> &s_,const vector<vector<int> > &r,vector<vector<P> > &b){
	int result=0;
	rep(i,K){
		int x=i;
		rep(j,H){
			if(r[x][j]==1){
				b[x][j].first=i;
				++x;
			} else if(x!=0&&r[x-1][j]==1){
				b[x-1][j].second=i;
				 --x;
			}
		}
		s_[i]=s[x];
		result+=s[x];
	}
	return result;
}

int solve(const vector<int> &s,const vector<int> &s_,vector<vector<int> > &vvi,const vector<vector<P> > &b,const int X,const int Y){
	int result=0;
	result-=(isIn(b[X][Y].first)?s_[b[X][Y].first]:0)+(isIn(b[X][Y].second)?s_[b[X][Y].second]:0);
	vvi[X][Y]=0;
	if(isIn(b[X][Y].first)){
		int x=b[X][Y].first;
		rep(i,H){
			if(vvi[x][i]==1) ++x;
			else if(x!=0&&vvi[x-1][i]==1) --x;
		}
		result+=s[x];
	}
	if(isIn(b[X][Y].second)){
		int x=b[X][Y].second;
		rep(i,H){
			if(vvi[x][i]==1) ++x;
			else if(x!=0&&vvi[x-1][i]==1) --x;
		}
		result+=s[x];
	}
	vvi[X][Y]=1;
	return result;
}

int main(){
	while(cin >> N >> M >> H >> K){
		if(N+M+H+K==0) break;
		vector<int> score(N);
		vector<int> score_(N);
		vector<vector<int> > rail(N,vector<int>(H)); //何番の棒を結ぶか、上端からの距離、横棒が存在するなら1
		vector<P> rail_(M); //横棒のx,yを保存
		rep(i,N) cin >> score[i];
		rep(i,M){
			int a,b;
			cin >> a >> b;
			--a;
			rail_[i].first=a;
			rail_[i].second=b;
			rail[a][b]=1;
		}
		vector<vector<P> > bar(N,vector<P>(H,P(-1,-1))); //x,yにある横棒とつながっているスタート地点の番号
		int ans,sum;
		ans=sum=pre(score,score_,rail,bar);
		rep(i,M){
			ans=min(ans,sum+solve(score,score_,rail,bar,rail_[i].first,rail_[i].second));
		}
		cout << ans << endl;
	}
	return 0;
}