// -*- coding:utf-8; tab-width:4 -*-
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <limits>
#include <complex>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>

// 解答
namespace solution {
    using namespace std;

    typedef istringstream ISS;
    typedef ostringstream OSS;
    typedef vector<string> VS;
    typedef long long LL;
    typedef int INT;
    typedef vector<INT> VI;
    typedef vector<VI> VVI;
    typedef pair<INT, INT> II;
    typedef map<string, int> TABLE;

    const int V_SIZE = 1001;
    const int D_SIZE = 1001;
    const int INF = INT_MAX/3;
    int m, n, k, d;
    int C[V_SIZE];
    string A[D_SIZE];
    string B[D_SIZE];
    int W[D_SIZE];

    TABLE T;
    int TC;

    class Graph {
    public:
        typedef pair<int,int> Edge;
        typedef vector<int> Edges;
        vector<Edges> G;
        vector<vector<int> > costs;
        Graph( int n = 0 ) {
            G = vector<Edges>(n);
            costs = vector<vector<int> >( n, vector<int>( n, INF ) );
        }
        void set_cost( int a, int b, int cost ) {
            costs[a][b] = costs[b][a] = cost;
        }
        int get_cost( int a, int b ) {
            return costs[a][b];
        }
        void add_edge( int a, int b, int cost ) {
            G[a].push_back(b);
            G[b].push_back(a);
            set_cost( a, b, cost );
        }
        int size() {
            return G.size();
        }
        vector<int>::iterator begin( int k ) {
            return G[k].begin();
        }
        vector<int>::iterator end( int k ) {
            return G[k].end();
        }
    };

    void add_node( string s ) {
        if ( T.count(s) )
            return;
        T[s] = TC;
        TC ++;
    }

    int find_node( string s ) {
        return T[s];
    }

    Graph G;

    int BellmanFord( Graph& g, int src, int dest ) {
        int dist[TC][1<<m];
        for ( int i = 0; i < TC; ++ i )
            for ( int j = 0; j < ( 1 << m ); ++ j )
                dist[i][j] = INF;
        bool used[TC][1<<m];
        for ( int i = 0; i < TC; ++ i )
            for ( int j = 0; j < ( 1 << m ); ++ j )
                used[i][j] = false;
        dist[src][0] = 0;
        used[src][0] = true;

        while ( true ) {
            bool update = false;
            bool next[TC][1<<m];
            for ( int i = 0; i < TC; ++ i )
                for ( int j = 0; j < ( 1 << m ); ++ j )
                    next[i][j] = false;

            for ( int i = 0; i < TC; ++ i ) {
                for ( int j = 0; j < ( 1 << m ); ++ j ) {
                    if ( ! used[i][j] )
                        continue;
                    for ( vector<int>::iterator it_i = G.begin(i); it_i != G.end(i); ++ it_i ) {
                        int e = *it_i;
                        if ( m <= e ) {
                            int new_dist = dist[i][j] + G.get_cost( i, e );
                            if ( new_dist < dist[e][j] ) {
                                dist[e][j] = new_dist;
                                update = true;
                                next[e][j] = true;
                            }
                        } else {
                            int be = 1 << e;
                            if ( j & be )
                                continue;
                            int new_dist = dist[i][j] + G.get_cost( i, e ) - C[e];
                            int nj = j | be;
                            if ( new_dist < dist[e][nj] ) {
                                dist[e][nj] = new_dist;
                                update = true;
                                next[e][nj] = true;
                            }
                        }
                    }
                }

            }
            for ( int i = 0; i < TC; ++ i )
                for ( int j = 0; j < ( 1 << m ); ++ j )
                    used[i][j] = next[i][j];

            if ( ! update )
                break;
        }

        int res = INF;
        for ( int i = 0; i < ( 1 << m ); ++ i ) {
            res = min( res, dist[dest][i] );
        }
        return res;
    }

    struct Solution {
        void init() {
            T.clear();
            TC = 0;
        }

        bool input() {
            cin >> m >> n >> k >> d;
            if ( m == 0 && n == 0 && k == 0 && d == 0 )
                return false;
            for ( int i = 0; i < m; ++ i ) {
                cin >> C[i];
            }
            for ( int i = 0; i < d; ++ i ) {
                cin >> A[i] >> B[i] >> W[i];
            }
            return true;
        }

        string to_string( int n ) {
            OSS oss;
            oss << n;
            return oss.str();
        }

        int solve() {
            for ( int i = 0; i < m; ++ i ) {
                add_node( "C"+to_string(i+1) );
            }
            add_node("H");
            add_node("D");
            for ( int i = 0; i < n; ++ i ) {
                add_node( "L"+to_string(i+1) );
            }

            G = Graph(TC);
            for ( int i = 0; i < d; ++ i ) {
                int a = find_node(A[i]);
                int b = find_node(B[i]);
                G.add_edge( a, b, W[i] * k );
            }

            return BellmanFord( G, find_node("H"), find_node("D") );
        }

        int run() {
            while ( init(), input() ) {
                cout << solve() << endl;
            }
            return 0;
        }
    };
}

int main() {
    return solution::Solution().run();
}

Measured memory_bytes: 1528