#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <sstream>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef long long ll;

const int MAX_SIZE = 10000;

struct edge{
	int to;
	int cost;
};

class Situation{
public:
	int cost;
	int idx;
	//bool cake[10];
	int used;
	
	Situation(int cost_,int idx_){
		cost=cost_;
		idx=idx_;
//		fill(cake,cake+10,false);
		used=0;
	}
	Situation();

	bool operator<(const Situation &s)const{
		return s.cost < this->cost;
	}
};

struct Kind{
	char k;
	int number;
};

int V;
const int MAX_V = 5000;

vector<edge> G[MAX_V];
Kind kind[MAX_V];

int d[MAX_V][256];
const int INF = 100000000;

int prevv[MAX_V];
// ツケツーツキツづ「ツづ湘氾ッツつキツづゥツカツδ債δ環ー
int cal[MAX_V];
int pk;

void dijkstra(int s){
	priority_queue<Situation> que;
	for(int i = 0; i < 256; i++)
		fill(d[i],d[i]+MAX_V,INF);
	fill(prevv,prevv+MAX_V,-1);
	d[s][0] = 0;
	que.push(Situation(0,s));
	while(!que.empty()){
		Situation p = que.top();
		que.pop();
		int v = p.idx;
		int used=p.used;

		if(d[v][used]<p.cost)
			continue;
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			// ツ行ツつォツ静ヲツつェツケツーツキツ可ョツつゥツづつ、ツつゥ
			if(kind[e.to].k=='C'&&((used>>kind[e.to].number)&1)){
				continue;
			}
			if(kind[e.to].k=='C'){
				if(d[e.to][(used | 1<<kind[e.to].number)] > p.cost + e.cost*pk - cal[kind[e.to].number]){
					d[e.to][(used | 1<<kind[e.to].number)] = p.cost + e.cost*pk- cal[kind[e.to].number];
					Situation sit=p;
					sit.cost=d[e.to][used | 1<<kind[e.to].number];
					sit.idx=e.to;
					sit.used=(used | 1<<kind[e.to].number);
					//for(int i = 0; i < 10; i++){
					//	sit.cake[i]=p.cake[i];
					//}
					//sit.cake[kind[e.to].number]=true;
					que.push(sit);
					// ツつサツづ個ノツーツドツづ鳴づ個催短ツ仰猟猟」ツ経ツ路ツづーツ記ツ録ツつオツづつィツつュ
					prevv[e.to] = v;
				}
			}
			else{
				if(d[e.to][used] > p.cost+ e.cost*pk){
					d[e.to][used] = p.cost + e.cost*pk;
					Situation sit=p;
					//for(int i = 0; i < 10; i++){
					//	sit.cake[i]=p.cake[i];
					//}
					sit.cost=d[e.to][used];
					sit.idx=e.to;
					que.push(sit);
					// ツつサツづ個ノツーツドツづ鳴づ個催短ツ仰猟猟」ツ経ツ路ツづーツ記ツ録ツつオツづつィツつュ
					prevv[e.to] = v;
				}
			}
		}
	}
}


int main(){

	int n,m,k,dd;
	while(cin>>m>>n>>k>>dd&&!(m==0&&n==0&&k==0&&dd==0)){
		for(int i = 1; i <= m; i++)
			cin>>cal[i];
		map<string,int> nodes;
		pk=k;
		int start;
		int goal;
		int idx=0;
		for(int i = 0; i < dd; i++){
			string s[2];
			int cost;
			cin>>s[0]>>s[1]>>cost;
			for(int j = 0; j < 2; j++){
				if(nodes.find(s[j])==nodes.end()){
					if(s[j][0]=='H'){
						start=idx;
						nodes["H"]=idx;
						kind[idx].k='H';
						kind[idx].number=0;
					}
					else if(s[j][0]=='D'){
						goal=idx;
						nodes["D"]=idx;
						kind[idx].k='D';
						kind[idx].number=0;
					}
					else if(s[j][0]=='L'){
						nodes[s[j]]=idx;
						kind[idx].k='L';
						kind[idx].number=atoi(s[j].substr(1).c_str());
					}
					else if(s[j][0]=='C'){
						nodes[s[j]]=idx;
						kind[idx].k='C';
						kind[idx].number=atoi(s[j].substr(1).c_str());
					}
					idx++;
				}
			}
			edge e;
			e.to = nodes[s[1]];
			e.cost=cost;
			G[nodes[s[0]]].push_back(e);
			e.to=nodes[s[0]];
			G[nodes[s[1]]].push_back(e);
		}

		dijkstra(start);

		int minNum=INF;
		for(int i = 0; i < 256; i++)
			minNum=min(minNum,d[goal][i]);
		cout<<minNum<<endl;

		for(int i = 0; i < idx; i++)
			G[i].clear();
	}

	return 0;
}

Measured memory_bytes: 0