一日乗車券

某国に住む大学生D氏は，国民的ギタリストA氏の大ファンで，この夏都心で行われるライブに行こうと考えている． しかし，D氏は辺境の地に住んでいるため，交通費がかかることがとても不安だった． そんなとき彼は，JAGという組織から安価で販売されている「1Dayパスポート」の存在を知った．

JAG (Journey Administrative Group) は，D氏が住む国に存在するいくつかの鉄道会社を統括する組織である． JAGは，全国に複数の駅を持ち，それらの間を結ぶ路線を整備している． 各路線は，JAGに所属する会社の内いずれか1社により管理されており，2駅間を途中駅無しで双方向に結んでいる． また各路線には，利用する際の運賃と所要時間が定まっている (これらはどちら向きに移動する場合でも等しい)． JAGのダイヤはシンプルに作られており，列車は毎時0分に駅に発着する． またJAGの各駅は，極めて賢くデザインされており，路線の乗り換えにかかる時間は無視することができる． 移動に必要な交通費は運賃の単純な合計となる.

1Dayパスポートは，JAGが昨今の経営難を脱するために販売し始めた，乗り放題パスポートである． JAGは，何種類かの1Dayパスポートを販売している． 各パスポートは，JAGが指定する販売価格で購入することができる． またパスポートには，JAGに所属する会社名がいくつか書かれており，これらの会社が管理する全ての路線が1日間 (追加料金無しで) 乗り放題になる． パスポートは，いくつでも購入することができ，複数のパスポートを併用することができる． ただし，パスポートに書かれていない会社の管理路線を通る場合，その路線の運賃は通常通り必要となる．

D氏は，1Dayパスポートをうまく使い，なるべくお金をかけずライブ会場まで行きたいと考えている． また，彼は宿泊で余計にお金をかけるのが嫌なので，この国の1日である$H$時間以下でライブ会場まで辿り着きたいと考えている． しかし，彼は計算が得意ではないため，同じ大学の友人でプログラミングが得意なあなたに助けを求めて来た． 困っているD氏のために，次のようなプログラムを書いてあげよう．

JAGの路線情報と1Dayパスポートの情報が与えられたとき，D氏の最寄り駅からライブ会場の最寄り駅へ，$H$時間以下で移動するための最小費用 (パスポート代と運賃の合計の最小) を求めるプログラムを作成せよ． $H$時間以下で到達できない場合や，ライブ会場へ到達する経路がない場合は，-1を出力せよ．

Input

入力は，複数のデータセットから構成され，1つの入力に含まれるデータセットの数は150以下である． 各データセットの形式は次の通りである．

$N$ $M$ $H$ $K$
$a_1$ $b_1$ $c_1$ $h_1$ $r_1$
...
$a_M$ $b_M$ $c_M$ $h_M$ $r_M$
$S$ $T$
$P$
$l_1$ $d_1$ $k_{1,1}$ ... $k_{1,l_1}$
...
$l_P$ $d_P$ $k_{P,1}$ ... $k_{P,l_P}$

入力は全て整数値で与えられる．

まず，JAGの路線情報が与えられる． $N$ ($2 \le N \le 100$) は駅の数，$M$ ($1 \le M \le 500$) は路線の数，$H$ ($1 \le H \le 24$) は1日の時間，$K$ ($1 \le K \le 8$) はJAGに所属する会社数を表す． 各駅には，$1, 2, \ldots, N$ と番号がついている． また，各会社には，$1, 2, \ldots, K$ と番号がついている． 続いて $M$ 行にわたって路線情報が入力される． $a_i$ と $b_i$ ($1 \le a_i \lt b_i \le N$) が $i$ 番目の路線がつないでいる2つの駅を表す． $c_i$ ($1 \le c_i \le 10{,}000$) は $i$ 番目の路線の運賃，$h_i$ ($1 \le h_i \le H$) は路線の所要時間，$r_i$ ($1 \le r_i \le K$) は路線を管理している会社を表す． ある2つの駅を結ぶ路線が2本以上存在することはない．

次の行で，D氏の最寄り駅 $S$ と，A氏のライブ会場の最寄り駅 $T$ が与えられる ($1 \le S, T \le N$)． $S$ と $T$ は異なる値である．

次に，1Dayパスポートの情報が与えられる． $P$ ($0 \le P \le 2^K - 1$) は，1Dayパスポートの種類数を表している． 続いて $P$ 行にわたって，1Dayパスポートの情報が入力される． $l_j$ ($1 \le l_j \le K$) と $d_j$ ($1 \le d_j \le 10{,}000$) は，それぞれ $j$ 番目の1Dayパスポートに書かれている会社数とパスポートの料金を表す． 同じ行に，$j$ 番目のパスポートに書かれた $l_j$ 個の会社番号 $k_{j, 1}, k_{j, 2}, \ldots, k_{j, l_j}$ ($1 \le k_{j, 1} \lt k_{j, 2} \lt \cdots \lt k_{j, l_j} \le K$) が与えられる． 同じ会社の組み合わせからなる1Dayパスポートが複数入力されることはない．

入力の終わりは，$N=M=H=K=0$ の行によって表される． このデータは処理を行ってはならない．

Output

各データセットに対して，計算結果を1行で出力せよ． すなわち，D氏の最寄り駅からライブ会場の最寄り駅への経路が存在し $H$ 時間以内に到達できるのであれば，そのための最小の料金を，辿り着けないのであれば-1を出力せよ．

Sample Input

3 3 3 2
1 2 3 1 1
1 3 8 1 1
2 3 3 2 2
1 3
0
3 3 2 2
1 2 3 1 1
1 3 8 1 1
2 3 3 2 2
1 3
0
6 4 3 2
1 2 3 1 1
1 3 8 1 1
4 6 3 2 2
5 6 7 2 2
1 6
0
3 3 3 2
1 2 3 1 1
1 3 8 1 1
2 3 3 2 2
1 3
2
2 6 1 2
1 2 2
3 3 2 2
1 2 3 1 1
1 3 8 1 1
2 3 3 2 2
1 3
2
2 6 1 2
1 2 2
3 2 2 2
1 2 3 1 1
2 3 3 2 2
1 3
2
2 6 1 2
1 2 2
5 4 20 4
2 4 100 5 1
1 4 100 5 3
1 5 100 5 4
3 5 100 5 2
3 2
3
2 80 1 2
2 60 1 3
2 40 2 3
0 0 0 0

Output for Sample Input

6
8
-1
5
6
-1
200

---