#include "bits/stdc++.h"
using namespace std;

struct Edge {
	int from;
	int to;
	int cost;
};
struct Node {
	int id;
	int minus;
	vector<Edge>edges;
};
struct aa {
	int now;
	int kal;
	bitset<6>used;
};
class Compare {
public:
	bool operator()(const aa&l, const aa&r) {
		return l.kal > r.kal;
	}
};
int M, N, K, D;
int getid(string st) {
	if (st[0] == 'H')return M + N;
	if (st[0] == 'D')return M + N + 1;
	else if (st[0] == 'C')return st[1] - '1';
	else return stoi(st.substr(1))-1 + M;
}

int main() {
	while (1) {
		cin >> M >> N >> K >> D;
		if (!M)break;
		vector<Node>nodes(M + N + 2);
		for (int i = 0; i < M; ++i) {
			int c; cin >> c;
			nodes[i].minus = c;
		}
		const int start = M + N;
		const int goal = M+N+1;
		for (int i = 0; i < D; ++i) {
			string s, t;int e; cin >> s >> t >> e;
			int sid = getid(s), tid(getid(t));
			e *= K;
			nodes[sid].edges.push_back(Edge{ sid,tid,e });
			nodes[tid].edges.push_back(Edge{ tid,sid,e });
		}
		priority_queue<aa,vector<aa>,Compare>que;
		vector<vector<int>>memo(M + N + 2, vector<int>(1 << 6, 1e8));
		memo[start][0] = 0;
		que.push(aa{ start,0,bitset<6>() });
		int ans = 1e8;
		while (!que.empty()) {
			aa atop(que.top());
			que.pop();
			if (atop.now == goal)ans = min(ans, atop.kal);
			for (auto e : nodes[atop.now].edges) {
				bitset<6>nextused(atop.used);
				int nextkal = atop.kal + e.cost;
				
				int nextid = e.to;
				if (nextid < M) {
					if (!nextused[nextid]) {
						nextused[nextid] = true;
						nextkal -= nodes[nextid].minus;
					}
					else {
						continue;
					}
				}
				if (memo[nextid][nextused.to_ulong()]>nextkal) {
					memo[nextid][nextused.to_ulong()] = nextkal;
					que.push(aa{ nextid,nextkal,nextused });
				}
			}
		}
		cout << ans << endl;

	}
	return 0;
}