#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-9;

int dp[1<<6][110];
int m, n, k, d;
vector<pii> g[110]; // [0,m):??±???????±?, [m,m+n):??????????????????, m+n:??????, m+n+1:?????????
int c[6];

int input() {
	char ch;
	int num;
	scanf(" %c", &ch);
	if (ch == 'H') return m + n;
	if (ch == 'D') return m + n + 1;
	scanf("%d", &num);
	
	int res = num - 1;
	if (ch == 'L') res += m;
	return res;
}

int main() {
	while (cin >> m >> n >> k >> d, m || n || k || d) {
		REP(i, m) scanf("%d", c + i);
		
		REP(i, m + n + 2) g[i].clear();
		
		REP(i, d) {
			int u = input();
			int v = input();
			int e; scanf("%d", &e);
			
			g[u].push_back(pii(v, e * k));
			g[v].push_back(pii(u, e * k));
		}
		
		
		fill(dp[0], dp[1<<m], INF);
		priority_queue<pip, vector<pip>, greater<pip> > pq;
		pq.push(pip(0, pii(0, m + n)));
		dp[0][m + n] = 0;
		
		while (!pq.empty()) {
			pip now = pq.top(); pq.pop();
			
			int s = now.se.fi;
			int u = now.se.se;
			
			REP(i, g[u].size()) {
				int v = g[u][i].fi;
				int nc = now.fi + g[u][i].se;
				
				if (v < m && s >> v & 1) continue;
				int ns = s;
				if (v < m) ns |= 1<<v;
				
				if (!chmin(dp[ns][v], nc)) continue;
				pq.push(pip(nc, pii(ns, v)));
			}
		}
		
		int ans = INF;
		REP(i, 1 << m) if (dp[i][n + m + 1] != INF) {
			int sum = 0;
			REP(j, m) if (i >> j & 1) sum += c[j];
			chmin(ans, dp[i][n + m + 1] - sum);
		}
		
		cout << ans << endl;
	}
	return 0;
}