#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <bitset>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};

bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;


int m;

// ¹öª¢çÈ¢ê
vector<Weight> dijkstra2(const Graph &g, int s) {
  int n = g.size();
  vector<Weight> dist(n, INF);
  dist[s] = 0;
  priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
  for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.top(); Q.pop();
    if (dist[e.dst] < e.weight) continue;
    FOR(f,g[e.dst]) {
      if (dist[f->dst] > e.weight+f->weight) {
        dist[f->dst] = e.weight+f->weight;
        if (f->dst >= 2 && f->dst < 2+m) continue;
        Q.push(Edge(f->src, f->dst, e.weight+f->weight));
      }
    }
  }
  return dist;
}
 int n, k, d;

int hoge(string s) {
  if (s=="H") 
    return 0;
  else if (s=="D")
    return 1;
  else if (s[0] == 'C')
    return atoi(s.substr(1).c_str())+1;
  else
    return atoi(s.substr(1).c_str()) + m+1;
}

int main() { 
  while(cin >> m >>n>>k>>d,m||n||k||d) {
    int ca[m];
    REP(i,m) cin >> ca[i];
    Graph g(m+n+2);
    REP(i,d) {
      string s1, s2;
      int di;
      cin >> s1 >> s2 >> di;
      int a1 = hoge(s1);
      int a2 = hoge(s2);
      g[a1].push_back(Edge(a1,a2,di));
      g[a2].push_back(Edge(a2,a1,di));
    }
    Graph g2(m+2);
    REP(i,m+2) {
      vector<int> dist = dijkstra2(g, i);
      for (int j=i+1; j<m+2; ++j) {
        if (i==j) continue;
        if (dist[j] == INF) continue; 
        g2[i].push_back(Edge(i, j, dist[j]));
        g2[j].push_back(Edge(j, i, dist[j]));
        //   printf("%d, %d (%d)\n", i,j,dist[j]);
      }
    }

    int dp[1<<m][m];
    REP(S,1<<m)REP(i,m) dp[S][i] = INF;
    int ans = INF;
    FOR(it, g2[0]) {
      //printf("it->dst = %d\n", it->dst);
      if (it->dst != 1) {
        dp[1<<(it->dst-2)][it->dst-2] = min(dp[1<<(it->dst-2)][it->dst-2], -ca[it->dst-2]+it->weight*k);
        //       cout << it->dst-2 << ": " << dp[1<<(it->dst-2)][it->dst-2] << endl;
      }
      else {
        ans = it->weight * k;
        FOR(jt, g2[1]) {
          if (jt->dst == 0) continue;
          dp[1<<(jt->dst-2)][jt->dst-2] = min(dp[1<<(jt->dst-2)][jt->dst-2], -ca[jt->dst-2] + (it->weight + jt->weight)*k);
          // cout << " " << jt->dst-2 << ": " << dp[1<<(jt->dst-2)][jt->dst-2] << endl;
        }
      }
    }
    REP(S, 1<<m) {
      REP(i,m) {
        if (!(S&(1<<i))) continue;
        // cout << bitset<3>(S).to_string() << " " << i << endl;
        FOR(it, g2[i+2]) {
          //printf("it->dst = %d\n", it->dst);
          if (it->dst == 1) {
            ans = min(ans, dp[S][i] + it->weight*k);
            FOR(jt, g2[1]) {
              if (jt->dst==0) continue;
              if (S & (1<<(jt->dst-2))) continue;
              dp[S | (1<<(jt->dst-2))][jt->dst-2] = min(dp[S | (1<<(jt->dst-2))][jt->dst-2], dp[S][i] -ca[jt->dst-2] + (it->weight + jt->weight)*k);
              //  cout << " " << jt->dst-2 << ": " << dp[S|1<<(jt->dst-2)][jt->dst-2] << endl;
            }
          } else if (it->dst == 0) {
            FOR(jt, g2[0]) {
              if (jt->dst==1) {
                ans = min(ans, dp[S][i]+(it->weight+jt->weight) * k);
                continue;
              }
              if (S & (1<<(jt->dst-2))) continue;
              dp[S | (1<<(jt->dst-2))][jt->dst-2] = min(dp[S | (1<<(jt->dst-2))][jt->dst-2], dp[S][i] -ca[jt->dst-2] + (it->weight + jt->weight)*k);
              //cout << " " << jt->dst-2 << ": " << dp[S|1<<(jt->dst-2)][jt->dst-2] << endl;
            }
          } else {
            if (S & (1<<(it->dst-2))) continue;
            dp[S | (1<<(it->dst-2))][it->dst-2] = min(dp[S | (1<<(it->dst-2))][it->dst-2], dp[S][i] - ca[it->dst-2] + it->weight*k);
            // cout << it->dst-2 << ": " << dp[S | 1<<(it->dst-2)][it->dst-2] ;//
            // cout << dp[S][i] - ca[it->dst-2] + it->weight*k  << endl;
          }
          // cout << ans << endl;
        }
      }
    }
    cout  << ans << endl;
  }
}

Measured memory_bytes: 0