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

using namespace std;

const int MAX = 1001;
typedef pair<int,int> P;
typedef pair<P,P> PP;
vector<PP> V;
int goal[MAX];
int n,m,h,k;
int finish[MAX];

void init(){
  V.clear();
}


void make(){

  int nowpos[MAX];

  for(int i = 1; i < MAX; i++)
    nowpos[i] = i;

  for(int i = 0; i < V.size(); i++){
    PP pp = V[i];
    int m = pp.first.second;

    pp.second = P(nowpos[m],nowpos[m+1]);
    V[i] = pp;
    swap(nowpos[m],nowpos[m+1]);
  }

  for(int i = 1; i < MAX; i++)
    finish[nowpos[i]] = goal[i];
}

void print(){
  for(int i = 1; i <= n; i++)
    cout << finish[i] << " ";
  cout << endl;
}

void solve(){

  // print();
  int ans = 0;
  for(int i = 1; i <= k; i++)
    ans += finish[i];

  for(int i = 0; i < V.size(); i++){
    int sum = 0;
    P p = V[i].second;

    swap(finish[p.first],finish[p.second]);

    for(int i = 1; i <= k; i++)
      sum += finish[i];

    ans = min(ans,sum);

    swap(finish[p.first],finish[p.second]);
  }

  cout << ans << endl;
}

int main(){

  while(cin >> n >> m >> h >> k && n+m+h+k){
    init();

    for(int i = 1; i <= n; i++)
      cin >> goal[i];

    for(int i = 0; i < m; i++){
      P p;
      cin >> p.second >> p.first;
      PP pp = PP(p,P(0,0));
      V.push_back(pp);
    }
    sort(V.begin(),V.end());

    make();
    solve();
  }
  
  return 0;
}