## subroutines

def lower_bound(arr, key, i0 = 0, i1 = arr.length)
  lb = i0 - 1
  ub = i1

  while lb + 1 < ub
    m = (lb + ub) / 2
    if arr[m][0] >= key
      ub = m
    else
      lb = m
    end
  end
  ub
end

def calc_sum(hlines, si, m, k)
  si0 = si.clone

  (m - 1).downto(0) do |i|
    hl = hlines[i]
    if hl[2]
      a = hl[0]
      tmp = si0[a]; si0[a] = si0[a + 1]; si0[a + 1] = tmp
    end
  end

  (0...k).inject(0){|s, i| s + si0[i]}
end

### main

loop do
  n, m, h, k = gets.strip.split(' ').map{|s| s.to_i}
  break if (n | m | h | k) == 0

  si = n.times.map{gets.strip.to_i}
  #p si

  hlines = []

  m.times do
    a, b = gets.strip.split(' ').map{|s| s.to_i}
    hlines << [b, a - 1, true]
  end
  #p hall

  hlines.sort!{|a, b| a[0] <=> b[0]}
  #p hlines

  min_sum = calc_sum(hlines, si, m, k)

  for hl in hlines
    hl[2] = false
    sum = calc_sum(hlines, si, m, k)
    hl[2] = true

    min_sum = sum if min_sum > sum
  end

  puts min_sum
end