#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


const int SIZE = 22;
const int NONE = -1;

int w, h;
int SG[SIZE][SIZE]; 
bool CS[SIZE][SIZE][SIZE][SIZE]; 
int D[SIZE][SIZE][SIZE][SIZE];
int sr, sc, gr, gc;

void init() {
    for ( int i = 0; i < SIZE; ++ i ) {
        for ( int j = 0; j < SIZE; ++ j ) {
            SG[i][j] = NONE;
        }
    }
    for ( int i1 = 0; i1 < SIZE; ++ i1 ) {
        for ( int j1 = 0; j1 < SIZE; ++ j1 ) {
            for ( int i2 = 0; i2 < SIZE; ++ i2 ) {
                for ( int j2 = 0; j2 < SIZE; ++ j2 ) {
                    CS[i1][j1][i2][j2] = false; 
                }
            }
        }
    }
}

II getPosition( string s ) {
    replace( s.begin(), s.end(), '-', ' ' );
    ISS iss( s );
    char H_;
    int H;
    int V;
    iss >> H_ >> V;
    H = H_ - 'a';
    V --;
    return II( H, V );
}

void input() {
    int D_;
    cin >> D_; 

    for ( int i1 = 0; i1 < SIZE; ++ i1 ) {
        for ( int j1 = 0; j1 < SIZE; ++ j1 ) {
            for ( int i2 = 0; i2 < SIZE; ++ i2 ) {
                for ( int j2 = 0; j2 < SIZE; ++ j2 ) {
                    D[i1][j1][i2][j2] = D_;
                }
            }
        }
    }

    int ns;
    cin >> ns;
    for ( int i = 0; i < ns; ++ i ) {
        string s;
        cin >> s;
        II ret1 = getPosition( s );
        int r = ret1.first, c = ret1.second;
        int k;
        cin >> k;
        SG[r][c] = k;
    }

    int nc;
    cin >> nc;
    for ( int i = 0; i < nc; ++ i ) {
        string s1, s2;
        cin >> s1 >> s2;
        II ret1 = getPosition( s1 ), ret2 = getPosition( s2 );
        int r1 = ret1.first, c1 = ret1.second, r2 = ret2.first, c2 = ret2.second;
        CS[r1][c1][r2][c2] = true;
        CS[r2][c2][r1][c1] = true;
    }

    int nj;
    cin >> nj;
    for ( int i = 0; i < nj; ++ i ) {
        string s1, s2;
        cin >> s1 >> s2;
        II ret1 = getPosition( s1 ), ret2 = getPosition( s2 );
        int r1 = ret1.first, c1 = ret1.second, r2 = ret2.first, c2 = ret2.second;
        int d;
        cin >> d;
        D[r1][c1][r2][c2] += d;
        D[r2][c2][r1][c1] += d;
    }

    {
        string s1, s2;
        cin >> s1 >> s2;
        II ret1 = getPosition( s1 ), ret2 = getPosition( s2 );
        int r1 = ret1.first, c1 = ret1.second, r2 = ret2.first, c2 = ret2.second;
        sr = r1, sc = c1, gr = r2, gc = c2;
    }
}

void debug() {
    for ( int i = 0; i < h; ++ i ) {
        for ( int j = 0; j < w; ++ j ) {
            if ( SG[i][j] != NONE )
                cout << "(" << i << "," << j << ")ツづ可信ツ債?機ツつェツつ?づゥ" << ", k = " << SG[i][j] << endl; 
        }
    }
    for ( int i1 = 0; i1 < h; ++ i1 ) {
        for ( int j1 = 0; j1 < w; ++ j1 ) {
            for ( int i2 = 0; i2 < h; ++ i2 ) {
                for ( int j2 = 0; j2 < w; ++ j2 ) {
                    cout << "(" << i1 << ", " << j1 << ")-(";
                    cout << i2 << ", " << j2 << ") = " << D[i1][j1][i2][j2] << endl;
                }
            }
        }
    }
    cout << "ツ始ツ点-ツ終ツ点" << ": (" << sr << ", " << sc << ") / (" << gr << ", " << gc << ")" << endl;
}

typedef pair <II, II> NODE; 
typedef priority_queue <NODE, vector<NODE>, greater<NODE> > QUEUE;

const int dr[4] = { 0, 1, 0, -1 };
const int dc[4] = { 1, 0, -1, 0 };

bool V[102][4][SIZE][SIZE];
void solveInit() {
    for ( int i1 = 0; i1 < 102; ++ i1 ) {
        for ( int j1 = 0; j1 < 4; ++ j1 ) {
            for ( int i2 = 0; i2 < SIZE; ++ i2 ) {
                for ( int j2 = 0; j2 < SIZE; ++ j2 ) {
                    V[i1][j1][i2][j2] = false;
                }
            }
        }
    }
}

bool isValidPos( int r, int c ) {
    return r >= 0 && r < h && c >= 0 && c < w;
}

int solve() {
    solveInit();

    QUEUE Q;
    Q.push( NODE( II( 0, 0 ), II( sr, sc ) ) );
    V[0][0][sr][sc] = true;

    while ( ! Q.empty() ) {
        NODE node = Q.top();
        Q.pop();

        int steps = node.first.first;
        int dir = node.first.second;
        int r = node.second.first;
        int c = node.second.second;

        if ( r == gr && c == gc ) {
            return steps;
        }
        

        for ( int i = 0; i < 4; ++ i ) {
            int ndir = i;
            if ( dir == ( ndir + 2 ) % 4 ) continue;
            int nr = r + dr[ndir];
            int nc = c + dc[ndir];
            if ( ! isValidPos( nr, nc ) ) continue;
            if ( CS[r][c][nr][nc] ) continue;
            int nsteps = steps + D[r][c][nr][nc];
            if ( nsteps > 100 ) continue;
            if ( SG[nr][nc] != NONE ) {
                int k = SG[nr][nc];
                bool f = ( ndir == 1 ) || ( ndir == 3 );
                if ( ( nsteps / k ) % 2 == 1 ) f = !f;
                if ( ! f ) continue;
            }
            if ( V[nsteps][ndir][nr][nc] ) continue;
            V[nsteps][ndir][nr][nc] = true;
            NODE next( II( nsteps, ndir ), II( nr, nc ) );
            Q.push( next );
        }

    }
    
    return -1;
}

int main() {
    while ( cin >> h >> w ) {
        if ( w == 0 && h == 0 ) break;
        init();
        input();
        cout << solve() << endl;
    }
    return 0;
}

Measured memory_bytes: 2328