運送会社

白虎運送は会津若松市を代表する運送会社です。昨今の原油価格の高騰は運送会社にも多大なダメージを与え、運送会社各社では、できるだけ少ないガソリンで荷物を運ぶことが課題となっています。

白虎運送では、重い荷物を積んだトラックは、その走りだしに多くのエネルギーを必要とすることに着目しました。トラックが倉庫を出発してから一度も停止することなく目的地まで到達する経路の中で最短時間の経路を通ることで、ガソリンの節約ができると考えました。

あなたの仕事は、このような最短経路を計算できるカーナビを開発することです。作成するカーナビ用プログラムの仕様は以下のとおりです。

市内は、下図のように、東西方向の道路 M 本、南北方向の道路 N 本からなる格子で表し、格子の各交点は交差点を表します。
交差点のいくつかには東西 - 南北の方向に信号機が設置されており、一定の周期で青、赤のシグナルが点灯しています。
市内の交差点間を結ぶ道路には工事中で通過できない個所がいくつかあります。
トラックが交差点から交差点へ移動するのに必要な時間は一定ですが、渋滞している道路ではさらに長い時間がかかります。

市内の道路情報、トラックが交差点間を移動するのに必要な時間、信号機がある交差点と各信号機の周期、工事中の道路、渋滞している道路と渋滞度、白虎運送の倉庫(始点)と目的地(終点)の位置を入力とし、始点から終点までの最短の時間を出力するプログラムを作成して下さい。

図のように、東西の方向の道路はa、b、c、... と英小文字で名前が付けられ、南北の方向の道路は 1、2、3、... と整数で名前が付けられています。市内の交差点は、これらの英小文字と整数の組み合わせ H-V で指定されます。

例えば、市内の最北西の交差点は a-1 で指定されます。各信号は周期 k をもち、k 分ごとに切り替わります。東西が青ならば南北が赤で、南北が青ならば東西が赤です。黄色のシグナルは存在しません。トラックは二つの交差点を結ぶ道路を移動するのに D 分要しますが、その道路が渋滞している場合はさらに d 分の時間を要します。トラックは道路が工事中の場合は移動できません。

また、交差点に到達した時刻に、信号が赤の場合には進入できません。トラックは交差点でのみ、東、西、南、北に方向を変えることができますが、来た方向へは移動(Uターン)できません。道路は2方通行であり、トラックが行き来する時間、工事状況、渋滞度は2方向共通です。

初期状態として、トラックは東を向いていて、トラックが倉庫を出発する瞬間すべての信号機が南北の方向に青に切り替わるものとします。また、トラックは 100分以内で目的地に到達できるものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

M N
D
ns
H₁-V₁ k₁
H₂-V₂ k₂
:
H_ns-V_ns k_ns
nc
H₁₁-V₁₁ H₁₂-V₁₂
H₂₁-V₂₁ H₂₂-V₂₂
:
H_nc1-V_nc1 H_nc2-V_nc2
nj
H₁₁-V₁₁ H₁₂-V₁₂ d₁
H₂₁-V₂₁ H₂₂-V₂₂ d₂
:
H_nj1-V_nj1 H_nj2-V_nj2 d_nj
H_s-V_s H_d-V_d

１行目に道路の本数 M, N (2 ≤ M, N ≤ 20) が与えられます。２行目に、二つの交差点を結ぶ道路を移動するのに要する時間 D (1 ≤ D ≤ D, 整数) が与えられます。

３行目に信号機の数 ns が与えられます。続く ns 行に、i 個目の信号機の位置を表す英小文字と整数の組 H_i-V_i と周期 k (1 ≤ k ≤ 100) が与えられます。

続く行に、工事中の道路の数 nc が与えられます。続く nc 行に、i 個目の工事中の道路の２つの端点（交差点）を表す英小文字と整数の組 H_i1-V_i1 H_i2-V_i2 が与えられます。

続く行に、渋滞道路の数 nj が与えられます。続く nj 行に、i 個目の渋滞道路の２つの端点（交差点）を表す英小文字と整数の組 H_i1-V_i1 H_i2-V_i2 と時間 d_i (1 ≤ d_i ≤ 100) が与えられます。

最後の行に、始点の交差点 H_s-V_d と終点の交差点 H_d-V_d が与えられます。

データセットの数は 20 を超えません。

Output

データセット毎に最短時間を１行に出力します。

Sample Input

4 5
1
3
b-2 3
c-3 2
c-4 1
3
a-2 b-2
b-3 c-3
d-3 d-4
2
b-3 b-4 1
c-1 d-1 1
d-1 b-4
4 5
1
3
b-2 3
c-3 2
c-4 1
3
a-2 b-2
b-3 c-3
d-3 d-4
2
b-3 b-4 1
c-1 d-1 1
d-2 b-4
4 5
1
3
b-2 3
c-3 2
c-4 1
3
a-2 b-2
b-3 c-3
d-3 d-4
2
b-3 b-4 1
c-1 d-1 1
d-3 b-4
0 0

Output for the Sample Input

7
4
8

Source: https://onlinejudge.u-aizu.ac.jp/problems/0194