#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }

void solve(int n, int m){
    int d, ns;
    cin >> d >> ns;
    map<int, int> kousaten;
    map<pair<int, int>, int> G;
    for (int i = 0; i < ns; ++i) {
        char a; int b, k;
        scanf(" %c-%d %d", &a, &b, &k);
        kousaten[(a-'a'+1)*m+b] = k;
    }
    int nc;
    cin >> nc;
    for (int i = 0; i < nc; ++i) {
        char a, aa; int b, bb;
        scanf(" %c-%d %c-%d", &a, &b, &aa, &bb);
        G[{(a-'a'+1)*m+b, (aa-'a'+1)*m+bb}] = 200;
        G[{(aa-'a'+1)*m+bb, (a-'a'+1)*m+b}] = 200;
    }
    int nj;
    cin >> nj;
    for (int i = 0; i < nj; ++i) {
        char a, aa; int b, bb, D;
        scanf(" %c-%d %c-%d %d", &a, &b, &aa, &bb, &D);
        G[{(a-'a'+1)*m+b, (aa-'a'+1)*m+bb}] = d+D;
        G[{(aa-'a'+1)*m+bb, (a-'a'+1)*m+b}] = d+D;
    }
    int sy, sx, gy, gx;
    {
        char a, aa; int b, bb;
        scanf(" %c-%d %c-%d", &a, &b, &aa, &bb);
        sy = a-'a'+1, sx = b, gy = aa-'a'+1, gx = bb;
    }
    auto v = make_v(n+2, m+2, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            v[i+1][j+1] = 1;
        }
    }
    array<int, 4> dy{-1, 1, 0, 0}, dx{0, 0, -1, 1};
    auto dp = make_v(n+2, m+2, 101, 4, 0);
    auto dfs = [&](int y, int x, int t, int kk, auto &&f) -> void {
        for (int k = 0; k < 4; ++k) {
            int yy = y+dy[k], xx = x+dx[k];
            if(!v[yy][xx] || k == (kk^1)) continue;

            if(kousaten.count(yy*m+xx)){
                int K = kousaten[yy*m+xx];
                int D = G.count({y*m+x, yy*m+xx}) ? G[{y*m+x, yy*m+xx}] : d;
                if(t+D <= 100 && !dp[yy][xx][t+D][kk] && !(((t+D)%(2*K) < K)^(k < 2))){
                    dp[yy][xx][t+D][kk] = 1;
                    f(yy, xx, t+D, k, f);
                }
            }else {
                int D = G.count({y*m+x, yy*m+xx}) ? G[{y*m+x, yy*m+xx}] : d;
                if(t+D <= 100 && !dp[yy][xx][t+D][kk]){
                    dp[yy][xx][t+D][kk] = 1;
                    f(yy, xx, t+D, k, f);
                }
            }

        }
    };
    dp[sy][sx][0][3] = 1;
    dfs(sy, sx, 0, 3, dfs);
    for (int i = 0; i <= 100; ++i) {
        for (int k = 0; k < 4; ++k) {
            if(dp[gy][gx][i][k]){
                cout << i << "\n";
                return;
            }
        }
    }
}

int main() {
    int n, m;
    while(cin >> n >> m, n){
        solve(n, m);
    }
    return 0;
}


Measured memory_bytes: 6056