#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

const int MAXV = 200;
const int MAXM = 6;
const int INF = 1<<28;
int M, N, K, D, V;
int cal[MAXM];
int G[MAXV][MAXV];

void wf() {
  for(int k = M; k < V; ++k) {
    for(int i = 0; i < V; ++i) {
      for(int j = 0; j < V; ++j) {
	G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
      }
    }
  }
}

int main() {
  while(cin >> M >> N >> K >> D && (M|N|K|D)) {
    for(int i = 0; i < M; ++i) cin >> cal[i];
    fill(G[0], G[MAXV], INF);
    for(int i = 0; i < MAXV; ++i) G[i][i] = 0;
    V = M + 2 + N;
    int src = M;
    int dst = M+1;
    while(D--) {
      int v[2];
      for(int i = 0; i < 2; ++i) {
	int &a = v[i];
	char c;
	cin >> c;
	if(c == 'C') {
	  cin >> a;
	  --a;
	} else if(c == 'L') {
	  cin >> a;
	  --a;
	  a += M+2;
	} else if(c == 'H') {
	  a = src;
	} else if(c == 'D') {
	  a = dst;
	}
      }
      int d;
      cin >> d;
      G[v[0]][v[1]] = min(G[v[0]][v[1]], d);
      G[v[1]][v[0]] = min(G[v[1]][v[0]], d);
    }

    wf();
    vector<int> id;
    for(int i = 0; i < M; ++i) id.push_back(i);
    id.push_back(dst);

    int res = INF;
    do {
      int p = M;
      int c = 0;
      for(int i = 0; i < id.size(); ++i) {
	int np = id[i];
	if(G[p][np] == INF) {
	  c = INF;
	  break;
	}
	c += G[p][np]*K;
	if(np == dst) break;
	c -= cal[np];
	p = np;
      }
      res = min(res, c);
    } while(next_permutation(id.begin(), id.end()));
    cout << res << endl;
  }
  return 0;
}