1 Day Passport

D, a university student living in some country, is a huge fan of the national guitarist A and plans to attend a live concert held downtown this summer. But since D lives in a remote region, he was very worried about the travel cost. Then he learned about the "1Day Passport" sold cheaply by an organization called JAG.

JAG (Journey Administrative Group) oversees several railway companies in D's country. JAG has many stations nationwide and maintains lines connecting them. Each line is managed by one of the companies belonging to JAG and connects two stations in both directions with no intermediate station. Each line also has a fixed fare and travel time (the same in either direction). JAG's timetable is simple: trains arrive at and depart from stations at 0 minutes past every hour. Each JAG station is designed very efficiently, so the time to transfer between lines can be ignored. The travel cost is the simple sum of the fares.

The 1Day Passport is an unlimited-ride pass that JAG started selling to escape its recent financial trouble. JAG sells several kinds of 1Day Passports. Each passport can be bought at the price JAG sets. A passport also lists some company names belonging to JAG, and all lines managed by those companies can be ridden unlimited times for one day (at no extra charge). Any number of passports can be bought, and multiple passports can be used together. However, when passing through a line managed by a company not written on any passport, its fare must be paid as usual.

D wants to use 1Day Passports well to reach the concert venue while spending as little money as possible. He also dislikes spending extra money on lodging, so he wants to reach the venue within $H$ hours, which is one day in this country. But he is not good at calculation, so he asks you, his university friend who is good at programming, for help. For D's sake, write the following program.

Given JAG's line information and 1Day Passport information, write a program to find the minimum cost (minimum of the sum of passport prices and fares) to travel from D's nearest station to the concert venue's nearest station within $H$ hours. If he cannot arrive within $H$ hours, or there is no route to the concert venue, output -1.

The input consists of multiple data sets, and the number of data sets in one input is at most 150. The format of each data set is as follows.

$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}$

All input values are integers.

First, JAG's line information is given. $N$ ($2 \le N \le 100$) is the number of stations, $M$ ($1 \le M \le 500$) is the number of lines, $H$ ($1 \le H \le 24$) is the hours in one day, and $K$ ($1 \le K \le 8$) is the number of companies belonging to JAG. Stations are numbered $1, 2, \ldots, N$. Companies are numbered $1, 2, \ldots, K$. Then $M$ lines of line information follow. $a_i$ and $b_i$ ($1 \le a_i < b_i \le N$) are the two stations connected by the $i$-th line. $c_i$ ($1 \le c_i \le 10{,}000$) is the fare of the $i$-th line, $h_i$ ($1 \le h_i \le H$) is the travel time of the line, and $r_i$ ($1 \le r_i \le K$) is the company managing the line. There are no two or more lines connecting the same pair of stations.

The next line gives $S$, D's nearest station, and $T$, the station nearest to A's concert venue ($1 \le S, T \le N$). $S$ and $T$ are different values.

Next, 1Day Passport information is given. $P$ ($0 \le P \le 2^K - 1$) is the number of kinds of 1Day Passports. Then $P$ lines of 1Day Passport information follow. $l_j$ ($1 \le l_j \le K$) and $d_j$ ($1 \le d_j \le 10{,}000$) are the number of companies written on the $j$-th 1Day Passport and the passport price, respectively. On the same line, the $l_j$ company numbers $k_{j, 1}, k_{j, 2}, \ldots, k_{j, l_j}$ written on the $j$-th passport are given ($1 \le k_{j, 1} < k_{j, 2} < \cdots < k_{j, l_j} \le K$). No two 1Day Passports with the same set of companies are given.

The end of the input is indicated by a line with $N=M=H=K=0$. This data set must not be processed.

For each data set, output the result on one line. That is, if a route exists from D's nearest station to the station nearest to the concert venue and he can arrive within $H$ hours, output the minimum fare needed; otherwise output -1.