#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
typedef pair<int, pair<int, int> > PPII;
typedef pair<int, int> PII;
static const int INF = 1ll<<60;

int N,M,H,K;
vector<int> V[1005];
int a[1005];
int flg[1005][1005];
vector<int> pass[1005][1005];
int vi[1005];
int s;
int maxd;
int temp=0;
int ans=0;

void dfs(int n,int m,bool down){
    //cout<<n<<" "<<V[n][m]<<" "<<s<<endl;
    pass[n][V[n][m]].PB(s);
    if(V[n][m]==maxd+1){
        vi[s]=a[n];
        return ;
    }
    if(down==true&&m!=0){
        int it = lower_bound(V[n+1].begin(),V[n+1].end(),V[n][m])-V[n+1].begin();
        if(it==V[n+1].size()||flg[n][V[n][m]]==0||V[n+1][it]!=V[n][m]){
            it = lower_bound(V[n-1].begin(),V[n-1].end(),V[n][m])-V[n-1].begin();
            dfs(n-1,it,false);
        }
        else dfs(n+1,it,false);
    }
    else {
        int it = upper_bound(V[n].begin(),V[n].end(),V[n][m])-V[n].begin();
        dfs(n,it,true);
    }
}

signed main(){
    while(1){
        cin>>N>>M>>H>>K;
        if(N==0)break;
        for(int i=0;i<N;++i){
            cin>>a[i];
        }
        for(int i=0;i<M;++i){
            int A,B;
            cin>>A>>B;
            A--;
            maxd=max(maxd,B);
            V[A].PB(B);
            V[A+1].PB(B);
            flg[A][B]=1;
        }
        for(int i=0;i<N;++i){
            V[i].PB(0);
            V[i].PB(maxd+1);
        }
        for(int i=0;i<N;++i)sort(V[i].begin(),V[i].end());
        for(int i=0;i<N;++i){
            s=i;
            int it = lower_bound(V[i].begin(),V[i].end(),0)-V[i].begin();
            dfs(i,it,true);
        }
        for(int i=0;i<K;++i)temp+=vi[i];
        ans=temp;
        for(int i=0;i<N;++i){
            for(int j=0;j<V[i].size();++j){
                int it = lower_bound(V[i+1].begin(),V[i+1].end(),V[i][j])-V[i+1].begin();
                if(it>=V[i+1].size())continue;
                if(V[i+1][it]!=V[i][j])continue;
                //cout<<V[i+1][it]<<" "<<V[i][j]<<endl;
                if(pass[i][V[i][j]].size()!=2||pass[i+1][V[i][j]].size()!=2)continue;
                if(min(pass[i][V[i][j]][0],pass[i][V[i][j]][1])!=min(pass[i+1][V[i][j]][0],pass[i+1][V[i][j]][1]))continue;
                if(max(pass[i][V[i][j]][0],pass[i][V[i][j]][1])!=max(pass[i+1][V[i][j]][0],pass[i+1][V[i][j]][1]))continue;
                int p1=min(pass[i][V[i][j]][0],pass[i][V[i][j]][1]),p2=max(pass[i+1][V[i][j]][0],pass[i+1][V[i][j]][1]);
                //cout<<p1<<" "<<p2<<endl;
                if(p1>=K&&p2>=K)continue;
                if(p1<K&&p2<K)continue;
                //cout<<p1<<" "<<p2<<" "<<temp-vi[min(p1,p2)]+vi[max(p1,p2)]<<endl;
                if(p1>=K||p2>=K)ans=min(ans,temp-vi[min(p1,p2)]+vi[max(p1,p2)]);
            }
        }
        cout<<ans<<endl;
        ans=0;
        temp=0;
        maxd=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<V[i].size();++j){
                flg[i][V[i][j]]=0;
                pass[i][V[i][j]].clear();
            }
            V[i].clear();
            vi[i]=0;
        }
    }
}

Measured memory_bytes: 43156