#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <string.h>
using namespace std;
int bit[6]={1,2,4,8,16,32};
int cost[108][108];
//0-99/land
//100-105/cake
//106/home
//107/city
int change(string s){
	if(s=="H")return 106;
	if(s=="D")return 107;
	if(s[0]=='C')return 99+(s[1]-'0');
	int t=0;
	for(int i=1;i<s.size();i++){
		t*=10;
		t+=(s[i]-'0');
	}
	return t-1;
}

typedef pair<int,int>p;
//cost,pos
typedef pair<p,int>P;
//cost,pos,bit


int bit_che(int to,int b){
	if(99<to&&to<106){
		if(bit[to-100]&b)return 0;
	}
	return 1;
}


int main(){
	
	int m;//
	int n;//
	int k;//
	int d;//
	while(cin>>m,m){
		cin>>n>>k>>d;
		//cout<<"--------\n";
		int cake[6];
		for(int i=0;i<m;i++)cin>>cake[i];
		memset(cost,1000000,sizeof(cost));
		for(int i=0;i<d;i++){
			string s1,s2;
			int c;
			cin>>s1>>s2>>c;
			int a=change(s1),b=change(s2);
			
			cost[a][b]=c*k;
			cost[b][a]=c*k;
			//cout<<a<<" "<<b<<" "<<c*k<<endl;
		}
		int data[108][64];
		for(int i=0;i<108;i++){
			for(int j=0;j<64;j++){
				data[i][j]=2000000;
			}
		}
		//memset(data,2000000,sizeof(data));
		priority_queue<P, vector<P>, greater<P> > Q;
		Q.push(P(p(0,106),0));
		int ans=100000000;
		while(!Q.empty()){
			int cos=Q.top().first.first;
			int pos=Q.top().first.second;
			int b=Q.top().second;
			Q.pop();
			//cout<<"#"<<cos<<" "<<pos<<" "<<b<<endl;
			
			if(pos==107){
				ans=min(ans,cos);
			}
			
			if(99<pos&&pos<106){
				cos-=cake[pos-100];
				b+=bit[pos-100];
			}
			data[pos][b]=cos;
			
			for(int i=0;i<108;i++){
				
				if(cost[pos][i]<10000&&(bit_che(i,b))&&data[i][b]>cos+cost[pos][i]){
					Q.push(P(p(cos+cost[pos][i],i),b));
					
				}
				
			}
			
			
			
		}
		cout<<ans<<endl;
		
	}
	
	
	return 0;
}
