運送会社

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

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

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


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

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

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

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

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

Input

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

M N
D
ns
H1-V1 k1
H2-V2 k2
:
Hns-Vns kns
nc
H11-V11 H12-V12
H21-V21 H22-V22
:
Hnc1-Vnc1 Hnc2-Vnc2
nj
H11-V11 H12-V12 d1
H21-V21 H22-V22 d2
:
Hnj1-Vnj1 Hnj2-Vnj2 dnj
Hs-Vs Hd-Vd

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

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

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

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

最後の行に、始点の交差点 Hs-Vd と終点の交差点 Hd-Vd が与えられます。

データセットの数は 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