#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int a[108][108],b[108][64],x[6],l,m,n,o;
void fn(int p,int q,int r){
  int i;
  if(p==l+m+1&&q==(~((~0)<<l))){
    if(b[p][q]>r)
      b[p][q]=r;
  }else if(b[p][q]>r){
    b[p][q]=r;
    for(i=0;i<l+m+2;i++){
      if(a[p][i]!=-1){
	if(i<l){
	  if((q&(1<<i))==0)
	    fn(i,q|(1<<i),r+a[p][i]-x[i]);
	}else{
	  fn(i,q,r+a[p][i]);
	}
      }
    }
  }
  return;
}
int main(){
  int i,j;
  while(cin>>l>>m>>n>>o&&(l||m||n||o)){
    for(i=0;i<l;i++)
      cin>>x[i];
    memset(a,-1,sizeof(a));
    for(i=0;i<o;i++){
      int p,q,r;
      char s;
      cin>>s;
      if(0){
      }else if(s=='C'){
	cin>>p>>s;
	p--;
	if(0){
	}else if(s=='C'){
	  cin>>q>>r;
	  q--;
	}else if(s=='L'){
	  cin>>q>>r;
	  q+=l-1;
	}else if(s=='H'){
	  cin>>r;
	  q=l+m;
	}else if(s=='D'){
	  cin>>r;
	  q=l+m+1;
	}
      }else if(s=='L'){
	cin>>p>>s;
	p+=l-1;	
	if(0){
	}else if(s=='C'){
	  cin>>q>>r;
	  q--;
	}else if(s=='L'){
	  cin>>q>>r;
	  q+=l-1;
	}else if(s=='H'){
	  cin>>r;
	  q=l+m;
	}else if(s=='D'){
	  cin>>r;
	  q=l+m+1;
	}
      }else if(s=='H'){
	p=l+m;
	cin>>s;
	if(0){
	}else if(s=='C'){
	  cin>>q>>r;
	  q--;
	}else if(s=='L'){
	  cin>>q>>r;
	  q+=l-1;
	}else if(s=='D'){
	  cin>>r;
	  q=l+m+1;
	}
      }else if(s=='D'){
	p=l+m+1;
	cin>>s;
	if(0){
	}else if(s=='C'){
	  cin>>q>>r;
	  q--;
	}else if(s=='L'){
	  cin>>q>>r;
	  q+=l-1;
	}else if(s=='H'){
	  cin>>r;
	  q=l+m;
	}
      }
      a[p][q]=a[q][p]=r*n;
    }
    for(i=0;i<l+m+2;i++)
      for(j=0;j<(1<<l);j++)
	b[i][j]=1<<30;
    fn(l+m,0,0);
    int mn=1<<30;
    for(i=0;i<(1<<l);i++)
      mn=min(mn,b[l+m+1][i]);
    cout<<mn<<endl;
  }
  return 0;
}