// -*- 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;
    
    // @snippet<sh19910711/contest:io/config.cpp>
    namespace io {
        const std::string OUTPUT_VECTOR_DELIMITER = ",";
    }
    
    // @snippet<sh19910711/contest:io/vector.cpp>
    namespace io {
        template <typename T> std::ostream& operator <<( std::ostream& os, std::vector<T>& v ) {
            typedef typename std::vector<T>::iterator Iterator;
            for ( Iterator it_i = v.begin(); it_i != v.end(); ++ it_i ) {
                os << *it_i;
                if ( it_i + 1 != v.end() )
                    os << OUTPUT_VECTOR_DELIMITER;
            }
            return os;
        }
        template <typename T> std::istream& operator >>( std::istream& is, std::vector<T>& v ) {
            int n = v.size();
            for ( int i = 0; i < n; ++ i ) {
                is >> v[i];
            }
            return is;
        }
    }

    using namespace io;
    
    const int C_SIZE = 8;
    const int EDGES = 301;
    const int INF = INT_MAX / 3;
    
    int m;
    int n;
    int k;
    int d;
    int C[C_SIZE];
    string A[EDGES];
    string B[EDGES];
    int L[EDGES];

    map<string, int> T;
    int TC;
    
    class Edge {
    public:
        int a;
        int b;
        int weight;
        Edge( int a, int b, int weight ): a(a), b(b), weight(weight) {}
        friend ostream& operator << ( ostream& os, Edge& e ) {
            os << "{a = " << e.a << ", b = " << e.b << ", " << e.weight << "}";
            return os;
        }
    };
    typedef vector<Edge> Edges;

    class Graph {
    public:
        typedef vector<int> VI;
        typedef vector<VI> VVI;
        VVI G;
        VVI W;
        int n;
        Graph() {}
        Graph( int n, Edges edges ): n(n) {
            G = vector<vector<int> >(n);
            W = vector<vector<int> >( n, vector<int>( n ) );
            for ( Edges::iterator it_i = edges.begin(); it_i != edges.end(); ++ it_i ) {
                addEdge(*it_i);
            }
        }
        void addEdge( Edge e ) {
            G[e.a].push_back(e.b);
            G[e.b].push_back(e.a);
            W[e.a][e.b] = W[e.b][e.a] = e.weight;
        }
        int getCost( int u, int v ) {
            return W[u][v];
        }
        VI::iterator begin( int u ) {
            return G[u].begin();
        }
        VI::iterator end( int u ) {
            return G[u].end();
        }
    };

    namespace BellmanFord {
        typedef vector<int> VI;
        typedef vector<VI> VVI;
        Graph* G;
        VVI dist;
        VVI used;
        VVI next;
        int n;
        int m;
        void init( Graph* G_, int n_, int m_ ) {
            G = G_;
            n = n_;
            m = m_;
            dist = VVI( n, VI( 1<<m, INF ) );
            used = VVI( n, VI( 1<<m, false ) );
        }
        void build( int start ) {
            dist[start][0] = 0;
            used[start][0] = true;

            while ( true ) {
                bool update = false;
                next = VVI( n, VI( (1<<m), false ) );
                for ( int i = 0; i < n; ++ i ) {
                    for ( int j = 0; j < ( 1 << m ); ++ j ) {
                        if ( ! used[i][j] )
                            continue;
                        for ( VI::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->getCost( 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->getCost( 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;
                                }
                            }
                        }
                    }
                }
                if ( ! update )
                    break;
                used = next;
            }
        }
    };

    Graph G;
    
    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] >> L[i];
            }
            return true;
        }
        
        string to_string( int n ) {
            OSS oss;
            oss << n;
            return oss.str();
        }

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

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

        Edges get_edges() {
            Edges res;
            for ( int i = 0; i < d; ++ i ) {
                res.push_back(Edge( find_index(A[i]), find_index(B[i]), L[i] * k ));
            }
            return res;
        }
        
        int solve() {
            for ( int i = 0; i < m; ++ i )
                add_index("C"+to_string(i+1));
            for ( int i = 0; i < n; ++ i )
                add_index("L"+to_string(i+1));
            add_index("H");
            add_index("D");
            int n = TC;

            Edges edges = get_edges();
            G = Graph(n, edges);
            int start = find_index("H");
            int goal = find_index("D");
            BellmanFord::init( &G, n, m );
            BellmanFord::build( start );
            
            int res = INT_MAX; 
            for ( int i = 0; i < ( 1 << m ); ++ i ) {
                res = min( res, BellmanFord::dist[goal][i] );
            }
            return res;
        }
        
        int run() {
            while ( init(), input() ) {
                cout << solve() << endl;
            }
            return 0;
        }
    };
}

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

Measured memory_bytes: 1584