#include<iostream>
#include<vector>
using namespace std;
#define MAX 2000

int n,m,h,k;
int t[MAX][MAX];
int change[MAX];
int u[MAX];
vector<int> G[MAX],A,B;

void compute(){
  for(int i=0;i<n;i++)t[h][i]=i;

  for(int i=h-1;i>=0;i--){
    for(int j=0;j<n;j++)t[i][j]=t[i+1][j];
    for(int j=0;j<(int)G[i].size();j++){
      int w=G[i][j];
      swap(t[i][w],t[i][w+1]);
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<(int)G[i].size();j++){
      int w=G[i][j];
      A.push_back(t[i][w]);
      B.push_back(t[i][w+1]);
    }
  }
  //for(int i=0;i<=h;i++){    for(int j=0;j<n;j++){
  //  cout<<t[i][j]<<" ";    }    cout<<endl;  } cout<<endl;
  
}

void solve(){  
  compute();
  int mini=0;
  for(int i=0;i<k;i++)mini+=u[t[0][i]];
  for(int i=0;i<(int)A.size();i++){
    swap(u[A[i]],u[B[i]]);
    int sum=0;
    for(int j=0;j<k;j++) sum+=u[t[0][j]];
    mini=min(mini,sum);
    swap(u[A[i]],u[B[i]]);
  }
  cout<<mini<<endl;
}

void init(){
  A.clear();
  B.clear();
  for(int i=0;i<MAX;i++)G[i].clear();
}

int main(){
  while(1){
    cin>>n>>m>>h>>k;
    if(n==0&&m==0&&h==0&&k==0)break;
    h--;
    init();
    for(int i=0;i<n;i++)cin>>u[i];
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a>>b;
      a--,b--;
      G[b].push_back(a);
    }
    solve();
  }
  return 0;
}