while true
  n, m, h, k = gets.split.map(&:to_i)
  break if n == 0
  amd = Array.new(h){ Array.new(n) }
  score = n.times.map{ gets.to_i }
  m.times do
    a, b = gets.split.map(&:to_i)
    amd[b][a-1] = true
  end
  res = Array.new(n){ |i| i }
  bar = Array.new(n){ Array.new(n) }
  (h-1).downto(0) do |i|
    n.times do |j|
      if amd[i][j]
        res[j], res[j+1] = res[j+1], res[j]
        bar[res[j]][res[j+1]] = bar[res[j+1]][res[j]] = true
      end
    end
  end
  tmp = 0
  flag = Array.new(n)
  k.times do |i|
    tmp += score[res[i]]
    flag[res[i]] = true
  end
  ret = tmp
  n.times do |i|
    n.times do |j|
      if flag[i] && !flag[j] && bar[i][j]
        ret = [ret, tmp - score[i] + score[j]].min
      end
    end
  end
  p ret
end