### constant

MAX_INT = 1 << 30

### main

while true
  m, n, k, d = gets.strip.split(' ').map{|s| s.to_i}
  break if m == 0

  nodes = (1..m).map{|i| "C#{i}"} + ['H', 'D'] + (1..n).map{|i| "L#{i}"}
  nodehash = {}
  nodes.each_with_index{|nd, i| nodehash[nd] = i}
  #p nodes
  #p nodehash

  cals = []
  gets.strip.split(' ').each_with_index do |s, i|
    cals[nodehash["C#{i + 1}"]] = s.to_i
  end
  #p cals

  edges = nodes.map{[]}
  nbrs = nodes.map{[]}
  d.times do
    lc0, lc1, dist = gets.strip.split(' ')
    i0 = nodehash[lc0]
    i1 = nodehash[lc1]
    edges[i0][i1] = edges[i1][i0] = dist.to_i * k
    nbrs[i0] << i1
    nbrs[i1] << i0
  end
  #p edges
  #p nbrs

  max_bits = (1 << m) - 1

  dists = (0..max_bits).map{nodes.map{MAX_INT}}
  dists[0][m] = 0
  q = [[0, m]]

  while ! q.empty?
    bits, id = q.shift
    next if id == m + 1 && bits == max_bits

    for nid in nbrs[id]
      if nid < m
        b = 1 << nid
        next if (bits & b) != 0
        nbits = (bits | b)
        d = dists[bits][id] + edges[id][nid] - cals[nid]
        if dists[nbits][nid] > d
          dists[nbits][nid] = d
          q << [nbits, nid]
        end
      else
        d = dists[bits][id] + edges[id][nid]
        if dists[bits][nid] > d
          dists[bits][nid] = d
          q << [bits, nid]
        end
      end
    end
  end

  min_dist = (0..max_bits).map{|bits| dists[bits][m + 1]}.min
  puts min_dist
end