### 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, h, k)
  sum = 0

  for x in (0...k)
    y = 0
    while y < h
      pos = lower_bound(hlines[x], y)
      y, dx, flag = hlines[x][pos]
      x += dx if flag
      y += 1
    end
    sum += si[x]
  end

  sum
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 = n.times.map{[[h, 0, true]]}
  hall = []

  m.times do
    a, b = gets.strip.split(' ').map{|s| s.to_i}
    h0 = [b,  1, true]
    h1 = [b, -1, true]

    hlines[a - 1] << h0
    hlines[a] << h1
    hall << [h0, h1]
  end
  #p hall

  for x in (0...n)
    hlines[x].sort!{|a, b| a[0] <=> b[0]}
  end
  #p hlines

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

  for hp in hall
    hp[0][2] = hp[1][2] = false
    sum = calc_sum(hlines, si, h, k)
    hp[0][2] = hp[1][2] = true

    min_sum = sum if min_sum > sum
  end

  puts min_sum
end