//45
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cctype>
#include<cstdlib>

using namespace std;

int main(){
  for(int m,n,k,nd;cin>>m>>n>>k>>nd,m|n|k|nd;){
    int c[6];
    for(int i=0;i<m;i++){
      cin>>c[i];
    }
    int d[108][108];
    fill(d[0],d[108],1<<29);
    while(nd--){
      string st[2];
      int ds;
      cin>>st[0]>>st[1]>>ds;
      int sti[2];
      for(int i=0;i<2;i++){
	sti[i]=(st[i]=="H")?0
	  :(st[i]=="D")?1
	  :atoi(st[i].c_str()+1)+((st[i][0]=='C')?1:1+m);
      }
      d[sti[0]][sti[1]]=d[sti[1]][sti[0]]=ds;
    }
    for(int i=0;i<108;i++){
      if(i<2||2+m<=i){
	for(int j=0;j<108;j++){
	  for(int k=0;k<108;k++){
	    d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
	  }
	}
      }
    }
    int mc=1<<30;
    for(int i=0;i<1<<m;i++){
      vector<int> v;
      int cc=0;
      for(int j=0;j<m;j++){
	if(i>>j&1){
	  v.push_back(j+2);
	  cc-=c[j];
	}
      }
      do{
	int ccs=cc;
	vector<int> cv=v;
	cv.insert(cv.begin(),0);
	cv.push_back(1);
	for(int i=0;i<cv.size()-1;i++){
	  if(d[cv[i]][cv[i+1]]==1<<29){
	    ccs=1<<30;
	    break;
	  }
	  ccs+=d[cv[i]][cv[i+1]]*k;
	}
	mc=min(mc,ccs);
      }while(next_permutation(v.begin(),v.end()));
    }
    cout<<mc<<endl;
  }
  return 0;
}