#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1001001001;

int func(char str[], int m)
{
	char c = str[0];
	if(c=='C') return atoi(str+1) - 1;
	if(c=='H') return m;
	if(c=='D') return m+1;
	return m+1+atoi(str+1);
}

struct Data
{
	int pos, cost;
	Data(int p, int c) : pos(p), cost(c) {}
	bool operator< (const Data& d) const {
		return cost > d.cost;
	}
};

int main()
{
	int m, n, k, d;
	while(scanf("%d%d%d%d", &m, &n, &k, &d), m){
		int cake[6];
		rep(i, m)
			scanf("%d", &cake[i]);
		
		int G[108][108];
		rep(i, m+n+2)
			fill(G[i], G[i]+m+n+2, INF);
		
		rep(i, d){
			char str1[128], str2[128];
			int dist;
			scanf("%s%s%d", str1, str2, &dist);
			int a = func(str1, m), b = func(str2, m);
			G[a][b] = G[b][a] = dist;
		}
		
		int S[8][8];
		rep(i, m+2){
			fill(S[i], S[i]+m+2, INF);
			bool visited[108] = {false};
			priority_queue<Data> Q;
			Q.push(Data(i, 0));
			while(!Q.empty()){
				Data d = Q.top();
				Q.pop();
				if(visited[d.pos])
					continue;
				visited[d.pos] = true;
				if(d.pos < m+2)
					S[i][d.pos] = d.cost;
				if(d.cost==0 || m<=d.pos){
					rep(j, m+n+2){
						if(G[d.pos][j] != INF)
							Q.push(Data(j, d.cost+G[d.pos][j]));
					}
				}
			}
		}

		int dp[1<<6][8];
		rep(i, 1<<m)
			fill(dp[i], dp[i]+m+2, INF);
		dp[0][m] = 0;

		rep(mask, 1<<m){
			rep(i, m+2){
				if(i<m && (mask&(1<<i))==0)
					continue;
				rep(j, m+2){
					if(S[i][j] == INF)
						continue;
					int next = mask;
					int cost = dp[mask][i] + S[i][j] * k;
					if(j < m){
						if((mask&(1<<j))!=0)
							continue;
						next |= 1 << j;
						cost -= cake[j];
					}
					dp[next][j] = min(dp[next][j], cost);
				}
			}
		}

		int ans = INF;
		rep(i, 1<<m)
			ans = min(ans, dp[i][m+1]);
		printf("%d\n", ans);
	}
	return 0;
}