#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct Edge{
	int src,dst,weight;
	Edge(){}
	Edge(int s,int d,int w):src(s),dst(d),weight(w){}
	bool operator<(const Edge& e)const{return weight<e.weight;}
	bool operator>(const Edge& e)const{return weight>e.weight;}
};
ostream& operator<<(ostream& os,const Edge& e){
	return os<<'('<<e.src<<','<<e.dst<<','<<e.weight<<')';
}

bool BellmanFord(const vector<Edge>& es,int size,int begin,vi& dp)
{
	bool neg=false;
	dp[begin]=0;
	rep(k,size){
		neg=false;
		for(Edge e:es)
			if(dp[e.dst]>dp[e.src]+e.weight){
				dp[e.dst]=dp[e.src]+e.weight;
				neg=true;
			}
	}
	return neg;
}

int main()
{
	for(int m,n,k,d;cin>>m>>n>>k>>d,m|n|k|d;){
		vi cs(m);
		rep(i,m) cin>>cs[i];
		
		int start=2*m+n,goal=start+1,v=goal+1;
		vector<Edge> es;
		rep(i,1<<m) rep(j,m)
			if(!(i>>j&1))
				es.emplace_back(i*v+j,(i|1<<j)*v+m+j,-cs[j]);
		
		while(d--){
			string src,dst; int dist; cin>>src>>dst>>dist;
			int si=-1;
			if(src[0]=='H') si=start;
			if(src[0]=='D') si=goal;
			if(src[0]=='C') si=stoi(src.substr(1))-1;
			if(src[0]=='L') si=2*m+stoi(src.substr(1))-1;
			int di=-1;
			if(dst[0]=='H') di=start;
			if(dst[0]=='D') di=goal;
			if(dst[0]=='C') di=stoi(dst.substr(1))-1;
			if(dst[0]=='L') di=2*m+stoi(dst.substr(1))-1;
			rep(i,1<<m){
				int si2=si,di2=di;
				if(src[0]=='C') si2+=m;
				if(dst[0]=='C') di2+=m;
				es.emplace_back(i*v+si2,i*v+di,dist*k);
				es.emplace_back(i*v+di2,i*v+si,dist*k);
			}
		}
		
		int size=(1<<m)*v;
		vi dp(size,INFTY);
		BellmanFord(es,size,start,dp);
		
		int res=INFTY;
		rep(i,1<<m)
			res=min(res,dp[i*v+goal]);
		cout<<res<<endl;
	}
	
	return 0;
}