// ナニソレイミワカンナイ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

struct Edge{
    int to, cost, cake;
};

int M, N, K, D; // cake, landmark, calorie per meter, edge
int cs[6];
std::vector<Edge> G[200];
int d[200][1<<6];

int inputTwo(){
    char c;
    scanf("%c", &c);
    
    // printf("%c: ", c);

    int i;
    if(c == 'C'){
        scanf("%d", &i);
        i -= 1;
        // printf("%d\n", i);
        return i+2;
    }else if(c == 'L'){
        scanf("%d", &i);
        i -= 1;
        // printf("%d\n", i);
        return i+M+2;
    }else if(c == 'H'){
        // puts("");
        return 0;
    }else{
        // puts("");
        return 1;
    }
}

int main(){
    while(scanf("%d %d %d %d", &M, &N, &K, &D), M || N || K || D){

        REP(i, 200){G[i].clear();}
        std::fill(&d[0][0], &d[0][0]+200*(1<<6), INF);

        REP(i, M){
            scanf("%d", cs+i);
        }

        REP(i, D){
            int u, v;
            scanf("%*c");
            u = inputTwo();
            scanf("%*c");
            v = inputTwo();
            scanf("%*c");
        
            int d;
            scanf("%d", &d);


            if(2 <= u && u < M+2){
                G[v].push_back({u, K*d, u-2});
            }else{
                G[v].push_back({u, K*d, -1});
            }
            if(2 <= v && v < M+2){
                G[u].push_back({v, K*d, v-2});
            }else{
                G[u].push_back({v, K*d, -1});
            }
        }

        // REP(i, 2+M+N){
        //     printf("%d->\n", i);
        //     for(auto e : G[i]){printf("%d\n", e.to);}
        //     puts("");
        // }

        std::priority_queue<State, std::vector<State>, std::greater<State>> q;
        q.push(mp(0, mp(0, 0)));
        d[0][0] = 0;
        
        while(!q.empty()){
            State s = q.top(); q.pop();
            int calorie = s.first, u = s.second.first, state = s.second.second;

            for(auto e : G[u]){
                int v = e.to, cost = e.cost, cake = e.cake;
                if(cake == -1){
                    if(calorie + cost < d[v][state]){
                        d[v][state] = calorie + cost;
                        q.push(mp(d[v][state], mp(v, state)));
                    }
                }else if((state >> cake & 1) == 0 && calorie + cost - cs[cake] < d[v][state | 1 << cake]){
                    d[v][state | 1 << cake] = calorie + cost - cs[cake];
                    q.push(mp(d[v][state|1<<cake], mp(v, state|1<<cake)));
                }
            }
        }

        int res = INF;
        REP(i, 1<<M){res = std::min(res, d[1][i]);}

        std::cout << res << std::endl;
    }
}