Mr. A loves sweets, but recently his wife has told him to go on a diet. One day, when Mr. A went out from his home to the city hall, his wife recommended that he go by bicycle. There, Mr. A reluctantly went out on a bicycle, but Mr. A, who likes sweets, came up with the idea of ​​stopping by a cake shop on the way to eat cake.

If you ride a bicycle, calories are consumed according to the mileage, but if you eat cake, you will consume that much calories. The net calories burned is the calories burned on the bike minus the calories burned by eating the cake. Therefore, the net calories burned may be less than zero.

If you buy a cake at a cake shop, Mr. A will eat all the cake on the spot. Mr. A does not stop at all cake shops, but when he passes through the point where the cake shop exists, he always stops and buys and eats one cake. However, it's really tempting to pass in front of the same cake shop many times, so each cake shop should only be visited once. In addition, you may stop by the cake shop after passing the destination city hall, and then return to the city hall to finish your work, and you may visit as many times as you like except the cake shop.

Enter the map information from Mr. A's home to the city hall, a list of calories of cakes that can be eaten at the cake shop on the way, and the calories burned by traveling a unit distance, from leaving home to entering the city hall. Create a program that outputs the minimum net calories burned.

The map shows Mr. A's home and city hall, a cake shop and a landmark building. The input data representing the map contains a line consisting of a symbol representing the two points and the distance between them, when there is a road connecting Mr. A's home, city hall, cake shop and each point of the landmark. For example, if the distance between the 5th cake shop and the 3rd landmark is 10, the input data will contain a line similar to the following:


C5 L3 10


In this way, cake shops are represented by C, and landmarks are represented by L in front of the number. Also, Mr. A's home is represented by H and the city hall is represented by D. If the input data is given two points and the distance between them, advance between the two points in either direction. For example, in the example above, you can go from a cake shop to a landmark and vice versa. In addition, you must be able to reach the city hall from your home. Other input data given are the number of cake shops m, the number of landmarks n, the calories burned per unit distance k, and the cakes that can be bought at each of the first cake shop to the mth cake shop. The total number of m data representing calories and distance data d.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by four 0 lines. Each dataset is given in the following format:


m n k d
c1 c2 ... cm
s1 t1 e1
s2 t2 e2
::
sd td ed


Number of cake shops m (1 ≤ m ≤ 6), number of landmarks n (1 ≤ n ≤ 100), calories burned per unit distance k (1 ≤ k ≤ 5), distance data on the first line The total number d (5 ≤ d ≤ 256) is given.

The second line gives the calories ci (1 ≤ ci ≤ 100) of the cake you buy at each cake shop.

The following d line is given the distance data si, ti, ei (1 ≤ ei ≤ 20) between the i-th two points.

The number of datasets does not exceed 100.

Output

Outputs the minimum total calories burned on one line for each input dataset.

Example

Input

1 1 2 5
35
H L1 5
C1 D 6
C1 H 12
L1 D 10
C1 L1 20
2 1 4 6
100 70
H L1 5
C1 L1 12
C1 D 11
C2 L1 7
C2 D 15
L1 D 8
0 0 0 0


Output

1
-2

// @snippet<sh19910711/contest:headers.cpp>
#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>

// @snippet<sh19910711/contest:table/keymap.cpp>
namespace table {
    template <class Key, class Data> class KeyMappingTable {
    public:
        std::vector<Data> memory;
        void init( Key& limit ) {
            memory.resize(mapping(limit));
        }
        void fill( Data& value ) {
            std::fill( memory.begin(), memory.end(), value );
        }
        virtual int mapping( Key& key ) = 0;
        Data& operator []( Key& key ) {
            return memory[mapping(key)];
        }
        Data& operator =( Data& right ) {
            memory = right.memory;
        }
    };
}

// @snippet<sh19910711/contest:graph/config.cpp>
namespace graph {
    typedef int Weight;
    const Weight DEFAULT_WEIGHT = std::numeric_limits<Weight>().max() / 2;
}

// @snippet<sh19910711/contest:graph/interface.cpp>
namespace graph {
    class IGraph {
    public:
        virtual void init( int n ) = 0;
        virtual void addEdge( int from, int to ) = 0;
        virtual void addVertices() = 0;
        virtual void addEdges() = 0;
        virtual int countVertices() = 0;
        virtual Weight getEdgeCost( int from, int to ) = 0;
        virtual void setEdgeCost( int from, int to, Weight weight ) = 0;
        virtual Weight getVertexCost( int v ) = 0;
        virtual void setVertexCost( int v, Weight weight ) = 0;
    };
}

// @snippet<sh19910711/contest:graph/adjacent_list.cpp>
namespace graph {
    class AdjacentListGraph: public IGraph {
    public:
        typedef std::vector<int> VI;
        typedef std::vector<VI> Edges;
        typedef std::vector<Weight> Weights;
        typedef std::vector<Weights> EdgeWeights;
        typedef VI::iterator VertexIterator;
        
        Edges edges;
        EdgeWeights edge_weights;
        Weights vertex_weights;
        int num;
        
        void init( int n ) {
            num = n;
            edges.resize(num);
            vertex_weights.resize(num);
            edge_weights.resize(num);
            std::fill( edges.begin(), edges.end(), VI() );
            std::fill( edge_weights.begin(), edge_weights.end(), Weights( num ) );
            addVertices();
            addEdges();
        }
        void addEdge( int from, int to ) {
            edges[from].push_back(to);
        }
        void addEdge( int from, int to, Weight weight ) {
            addEdge( from, to );
            setEdgeCost( from, to, weight );
        }
        int countVertices() {
            return num;
        }
        Weight getVertexCost( int from ) {
            return vertex_weights[from];
        }
        void setVertexCost( int from, Weight weight ) {
            vertex_weights[from] = weight;
        }
        Weight getEdgeCost( int from, int to ) {
            return edge_weights[from][to];
        }
        void setEdgeCost( int from, int to, Weight weight ) {
            edge_weights[from][to] = weight;
        }
        VertexIterator begin( int from ) {
            return edges[from].begin();
        }
        VertexIterator end( int from ) {
            return edges[from].end();
        }
    };
}


template <class NODE, class DIST_TYPE, class VISITED_TYPE> class BellmanFord {
public:
    graph::AdjacentListGraph* G;
    DIST_TYPE dist;
    VISITED_TYPE visited;
    VISITED_TYPE next_visited;
    BellmanFord() {
    }
    virtual void init( graph::AdjacentListGraph* G ) {
        this->G = G;
    }
    void build( NODE start_node ) {
        dist[start_node] = 0;
        visited[start_node] = true;
        while ( true ) {
            if ( ! distribute() )
                break;
            visited = next_visited;
        }
    }
    virtual bool distribute() {
        return false;
    }
};

// @snippet<sh19910711/contest:solution/interface.cpp>
namespace solution {
    class ISolution {
    public:
        virtual void init() {};
        virtual bool input() { return false; };
        virtual void output() {};
        virtual int run() = 0;
    };
}

// @snippet<sh19910711/contest:solution/solution.cpp>
namespace solution {
    using namespace std;
    
    typedef vector<int> VI;
    
    class Node {
    public:
        int id;
        int state;
        Node( int id, int state ): id(id), state(state) {
        }
        friend ostream& operator << ( ostream& os, Node& node ) {
            os << "(" << node.id << ", " << node.state;
            return os;
        }
    };
    template <class T> class BF_TABLE: public table::KeyMappingTable<Node, T> {
    public:
        int n;
        int m;
        void init( int n_, int m_, T value ) {
            n = n_;
            m = m_;
            Node limit( n, m );
            table::KeyMappingTable<Node, T>::init( limit );
            table::KeyMappingTable<Node, T>::fill( value );
        }
        int mapping( Node& node ) {
            return node.id * m + node.state;
        }
    };
    class BELLMAN_FORD: public BellmanFord< Node, BF_TABLE<int>, BF_TABLE<char> > {
    public:
        int n;
        int m;
        void init( graph::AdjacentListGraph* G_, int m_ ) {
            G = G_;
            n = G->countVertices();
            m = m_;
            dist.init( n, 1 << m, graph::DEFAULT_WEIGHT );
            visited.init( n, 1 << m, false );
        }
        bool distribute() {
            bool updated = false;
            next_visited.init( n, 1 << m, false );
            for ( int i = 0; i < n; ++ i ) {
                for ( int j = 0; j < ( 1 << m ); ++ j ) {
                    Node node( i, j );
                    if ( ! visited[node] )
                        continue;
                    for ( VI::iterator it_i = G->begin(i); it_i != G->end(i); ++ it_i ) {
                        updated = updated | update( node, *it_i );
                    }
                }
            }
            return updated;
        }
        bool update( Node& node, int to ) {
            if ( m <= to ) {
                int new_dist = dist[node] + G->getEdgeCost( node.id, to );
                Node new_node( to, node.state );
                if ( new_dist < dist[new_node] ) {
                    dist[new_node] = new_dist;
                    next_visited[new_node] = true;
                    return true;
                }
            } else {
                int bit_to = 1 << to;
                if ( node.state & bit_to )
                    return false;
                int new_dist = dist[node] + G->getEdgeCost( node.id, to ) + G->getVertexCost( to );
                int new_state = node.state | bit_to;
                Node new_node( to, new_state );
                if ( new_dist < dist[new_node] ) {
                    dist[new_node] = new_dist;
                    next_visited[new_node] = true;
                    return true;
                }
            }
            return false;
        }
    };
    
    typedef ostringstream OSS;
    template <class T> string to_string( T s ) {
        OSS oss;
        oss << s;
        return oss.str();
    }
    
    const int CAKE_SHOPS = 7;
    const int EDGES = 301;
    
    int m, n, k, d;
    int calory[CAKE_SHOPS];
    string A[EDGES];
    string B[EDGES];
    int C[EDGES];
    
    class GRAPH: public graph::AdjacentListGraph {
    public:
        map <string, int> table;
        int table_count;
        void init( int n ) {
            table.clear();
            table_count = 0;
            AdjacentListGraph::init(n);
        }
        void addNewVertex( string s ) {
            if ( table.count(s) )
                return;
            table[s] = table_count ++;
        }
        int findVertex( string s ) {
            return table[s];
        }
        void addVertices() {
            for ( int i = 0; i < m; ++ i ) {
                addNewVertex( "C" + to_string(i+1) );
            }
            for ( int i = 0; i < n; ++ i ) {
                addNewVertex( "L" + to_string(i+1) );
            }
            addNewVertex("H");
            addNewVertex("D");
            for ( int i = 0; i < m; ++ i ) {
                setVertexCost( i, -calory[i] );
            }
        }
        void addEdges() {
            for ( int i = 0; i < d; ++ i ) {
                addEdge( findVertex(A[i]), findVertex(B[i]), C[i] * k );
                addEdge( findVertex(B[i]), findVertex(A[i]), C[i] * k );
            }
        }
    }; 
    
    class Solution: public ISolution {
    public:
        
        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 >> calory[i];
            for ( int i = 0; i < d; ++ i ) {
                cin >> A[i] >> B[i] >> C[i];
            }
            return true;
        } 
        int solve() {
            G.init( m + n + 2 );
            
            int start = G.findVertex("H");
            int goal = G.findVertex("D");
            Node start_node( start, 0 );
            
            BF.init( &G, m );
            BF.build( start_node );
            
            int res = numeric_limits<int>().max();
            for ( int i = 0; i < ( 1 << m ); ++ i ) {
                Node node( goal, i );
                res = min( res, BF.dist[node] );
            }
            return res;
        }
        void output( int result ) {
            cout << result << endl;
        }
        int run() {
            while ( init(), input() ) {
                output(solve());
            }
            return 0;
        }
    private:
        GRAPH G;
        BELLMAN_FORD BF;
    };
}

// @snippet<sh19910711/contest:main.cpp>

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