#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef pair<int,int> P;

#define INF (1e9)

void solve(int n,int m,int h,int k) {
    vector<P> amida;
    int ind[n];
    int s[n];
    vector<P> swp;
    unordered_set<int> check;

    for(int i=0; i<n; ++i) {
        cin >> s[i];
        ind[i]=i;
    }

    for(int i=0; i<m; ++i) {
        int a,b;
        cin >> a >> b;
        amida.push_back(P(b,a-1));
    }

    sort(amida.rbegin(),amida.rend());

    for(int i=0; i<m; ++i) {
        swap(ind[amida[i].second],ind[amida[i].second+1]);
        swp.push_back(
            P(min(ind[amida[i].second],ind[amida[i].second+1])
            ,max(ind[amida[i].second],ind[amida[i].second+1])));
    }

    int sum=0;
    for(int i=0; i<k; ++i) {
        sum+=s[ind[i]];
        check.insert(ind[i]);
    }

    int ans=sum;
    for(vector<P>::iterator itr=swp.begin(); itr!=swp.end(); ++itr) {
        if(check.count(itr->first)!=0 && check.count(itr->second)==0) {
            ans=min(ans,sum-s[itr->first]+s[itr->second]);
        } else if(check.count(itr->second)!=0 && check.count(itr->first)==0) {
            ans=min(ans,sum-s[itr->second]+s[itr->first]);
        }
    }

    cout << ans << endl;

    return;
}


int main() {
    int n,m,h,k;
    while(true) {
        cin >> n >> m >> h >> k;
        if(n==0 && m==0 && h==0 && k==0) break;
        solve(n,m,h,k);
    }
    return 0;
}
