#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> edge;
typedef pair<int,edge> state;

int toInt(string s){
  stringstream ss(s);
  int res;
  ss >> res;
  return res;
}

inline int id(string a,int m, int n){
  if(a[0] == 'C')return toInt(a.substr(1))-1;
  if(a[0] == 'L')return toInt(a.substr(1))-1 + m;
  if(a[0] == 'H')return n+m;
  return m+n+1;
}

int main(){
  int m,n,k,d;
  while(cin >> m >> n >> k >> d, n){
    vector<int> c(m);
    for(int i=0;i<m;i++)cin >> c[i];

    vector< vector<edge> > g(n+m+2);
    for(int i=0;i<d;i++){
      string A,B;
      int cost;
      cin >> A >> B >> cost;
      int a = id(A,m,n), b = id(B,m,n);

      g[a].push_back( edge(cost,b) );
      g[b].push_back( edge(cost,a) );
    }

    vector< vector<int> > dis(1<<m,vector<int>(n+m+2,1e8));
    dis[0][n+m] = 0;
    priority_queue< state,vector<state>,greater<state> > q;
    q.push(state(0,make_pair(0,n+m)));
    
    while(q.size()){
      state s = q.top(); q.pop();
      int cost = s.first, bit = s.second.first, pos = s.second.second;

      if(dis[bit][pos] < cost)continue;
      for(edge e : g[pos]){
	int nxtpos = e.second, nxtcost = cost + e.first, nxtbit = bit;
	if(nxtpos<m){
	  if((bit>>nxtpos)&1)continue;
	  nxtbit |= 1<<nxtpos;
	}
	if(dis[nxtbit][nxtpos] > nxtcost){
	  dis[nxtbit][nxtpos] = nxtcost;
	  q.push(state(nxtcost, make_pair(nxtbit,nxtpos)));
	}
      }
    }

    int res = 1e8;
    for(int bit=0;bit<(1<<m);bit++){
      int cake = 0;
      for(int i=0;i<m;i++){
	if((bit>>i)&1)cake += c[i];
      }
      res = min(res, dis[bit][n+m+1]*k - cake);
    }
    cout << res << endl;
  }
}