## 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 << [a - 1, b]
  end
  #p hall

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

  is = (0...n).to_a

  for hl in hlines
    a = hl[0]
    hl[2] = is[a]
    hl[3] = is[a + 1]

    tmp = is[a]; is[a] = is[a + 1]; is[a + 1] = tmp
  end

  si0 = si.clone

  for hl in hlines.reverse
    a = hl[0]
    hl[4] = si0[a]
    hl[5] = si0[a + 1]

    tmp = si0[a]; si0[a] = si0[a + 1]; si0[a + 1] = tmp
  end

  min_sum = sum = (0...k).inject(0){|sum, i| sum + si0[i]}

  for hl in hlines
    a, b, i0, i1, s0, s1 = hl

    if i0 < k && i1 >= k
      sum0 = sum - s1 + s0
      min_sum = sum0 if min_sum > sum0
    elsif i1 < k && i0 >= k
      sum0 = sum - s0 + s1
      min_sum = sum0 if min_sum > sum0
    end
  end

  puts min_sum
end