#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define P pair<int, int>
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
const int MAX_M = 6;
const int MAX_N = 100;
const int MAX_PRE_NODE = MAX_M + MAX_N + 5;
const int MAX_NODE = MAX_M + 5;
const int INF = 1e9;

int M, N, K, D, pre_cost[MAX_PRE_NODE][MAX_PRE_NODE], cost[MAX_NODE][MAX_NODE], cake[MAX_M], ans;

class C{
  public:
    int now, c;
    vector<bool> visited;
    C(int _c, int _n, vector<bool> _v){ now = _n; c = _c; visited = _v; }
    C(){}
    bool operator > (const C &cc) const { return c > cc.c; }
};

void dij(){
  priority_queue<C, vector<C>, greater<C> > open;
  vector<bool> tmp_v(M + 2, false);
  tmp_v[0] = true;
  open.push( C(0, 0, tmp_v) );
  int closed[MAX_NODE];
  REP(i, MAX_NODE) closed[i] = INF;
  while(!open.empty()){
    C tmp = open.top(); open.pop();
    int c = tmp.c, now = tmp.now;
    vector<bool> visited = tmp.visited;
    closed[now] = min(c, closed[now]);
    if(now != 0 && now != M + 1) c -= cake[now - 1];
    REP(i, M + 2){
      if(cost[now][i] == INF || (visited[i] && i != M + 1 && i != 0)) continue;
      visited[i] = true;
      open.push( C(c + cost[now][i], i, visited) );
      visited[i] = false;
    }
  }
  ans = closed[M + 1];
}

void dfs(int now, int c, vector<bool> &visited){
  //cout <<now <<", " <<c <<endl;
  //REP(i, M + 2) cout <<visited[i] <<" "; cout <<endl;
  //cout <<"-----" <<endl;
  if(now != 0 && now != M + 1) c -= cake[now - 1];
  if(now == M + 1 && ans <= c) return ;
  if(now == M + 1) ans = min(ans, c);
  REP(i, M + 2){
    if(cost[now][i] == INF || (i != M + 1 && visited[i] && i != 0)) continue;
    visited[i] = true;
    //cout <<"! " <<c <<" + " <<cost[now][i] <<endl;
    dfs(i, c + cost[now][i], visited);
    visited[i] = false;
  }
  //cout <<"back" <<endl;
}

int main() {
  while(cin >>M >>N >>K >>D && M){
    ans = INF;
    REP(i, MAX_PRE_NODE) REP(j, MAX_PRE_NODE) pre_cost[i][j] = INF;
    REP(i, MAX_NODE) REP(j, MAX_NODE) cost[i][j] = INF;
    REP(i, M) cin >>cake[i];
    REP(i, D){
      int from, to, c;
      char from_c, to_c;
      scanf(" %c", &from_c);
      if(from_c != 'D' && from_c != 'H') scanf("%d", &from);
      scanf(" %c", &to_c);
      if(to_c != 'D' && to_c != 'H') scanf("%d", &to);
      scanf("%d", &c);

      c *= K;
      if(from_c == 'H') from = 0;
      else if(from_c == 'D') from = M + N + 1;
      else if(from_c == 'L') from += M;
      if(to_c == 'H') to = 0;
      else if(to_c == 'D') to = M + N + 1;
      else if(to_c == 'L') to += M;
      //cout <<from <<", " <<to <<", " <<c <<endl;
      pre_cost[from][to] = c;
      pre_cost[to][from] = c;
    }

    REP(k, N + M + 2)
      REP(i, N + M + 2)
        REP(j, N + M + 2)
          if(k >= M + 1 && k <= M + N + 1) pre_cost[i][j] = min(pre_cost[i][j], pre_cost[i][k] + pre_cost[k][j]);
    //debug
    //REP(i, N + M + 2){
    //  REP(j, N + M + 2){
    //    cout <<pre_cost[i][j] <<" ";
    //  }
    //  cout <<endl;
    //}
    //cout <<"-------" <<endl;

    REP(i, M + 1){
      REP(j, M + 1){
        cost[i][j] = (i == j ? INF : pre_cost[i][j]);
      }
      cost[i][M + 1] = pre_cost[i][M + N + 1];
    }
    REP(j, M + 1)
      cost[M + 1][j] = pre_cost[M + N + 1][j];

    //REP(i, M + 2){
    //  REP(j, M + 2){
    //    cout <<cost[i][j] <<" ";
    //  }
    //  cout <<endl;
    //}
    //cout <<"-------" <<endl;

    vector<bool> visited(M + 2, false);
    visited[0] = true;
    dfs(0, 0, visited);
    //dij();
    cout <<ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 1304