1 Day Passport

어느 나라에 사는 대학생 D는 국민적 기타리스트 A의 열렬한 팬으로, 이번 여름 도심에서 열리는 라이브 공연에 가려고 한다. 그러나 D는 변경에 살기 때문에 교통비가 많이 들까 봐 매우 걱정했다. 그때 그는 JAG라는 조직이 저렴하게 판매하는 "1Day 패스포트"의 존재를 알게 되었다.

JAG (Journey Administrative Group)는 D가 사는 나라에 있는 여러 철도 회사를 총괄하는 조직이다. JAG는 전국에 여러 역을 두고, 역 사이를 잇는 노선을 운영한다. 각 노선은 JAG에 속한 회사 중 한 곳이 관리하며, 두 역을 중간 역 없이 양방향으로 연결한다. 또한 각 노선에는 이용할 때의 운임과 소요 시간이 정해져 있다 (어느 방향으로 이동해도 같다). JAG의 열차 운행은 단순해서, 열차는 매시 0분에 역에 도착하고 출발한다. 또 JAG의 각 역은 매우 효율적으로 설계되어, 노선을 갈아타는 데 걸리는 시간은 무시할 수 있다. 이동에 필요한 교통비는 운임의 단순한 합이다.

1Day 패스포트는 JAG가 최근의 경영난을 벗어나기 위해 판매하기 시작한 무제한 승차 패스포트이다. JAG는 여러 종류의 1Day 패스포트를 판매한다. 각 패스포트는 JAG가 지정한 판매 가격으로 살 수 있다. 또한 패스포트에는 JAG에 속한 회사 이름이 몇 개 적혀 있고, 이 회사가 관리하는 모든 노선을 하루 동안 (추가 요금 없이) 무제한으로 탈 수 있다. 패스포트는 몇 개든 살 수 있고, 여러 패스포트를 함께 쓸 수 있다. 다만 패스포트에 적히지 않은 회사가 관리하는 노선을 지나갈 경우, 그 노선의 운임은 평소대로 내야 한다.

D는 1Day 패스포트를 잘 활용해서 되도록 돈을 적게 쓰고 라이브 회장까지 가고 싶어 한다. 또한 숙박으로 돈을 더 쓰기 싫어서, 이 나라의 하루인 $H$시간 이내에 라이브 회장까지 도착하려고 한다. 그러나 그는 계산을 잘하지 못해서, 같은 대학 친구이자 프로그래밍을 잘하는 당신에게 도움을 청했다. 곤란해하는 D를 위해, 다음과 같은 프로그램을 작성해 주자.

JAG의 노선 정보와 1Day 패스포트 정보가 주어졌을 때, D의 가장 가까운 역에서 라이브 회장의 가장 가까운 역까지 $H$시간 이내에 이동하는 최소 비용 (패스포트 값과 운임 합계의 최솟값)을 구하는 프로그램을 작성하라. $H$시간 이내에 도달할 수 없거나 라이브 회장으로 가는 경로가 없으면 -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$)는 하루의 시간, $K$ ($1 \le K \le 8$)는 JAG에 속한 회사의 수를 나타낸다. 각 역에는 $1, 2, \ldots, N$의 번호가 붙어 있다. 또 각 회사에는 $1, 2, \ldots, K$의 번호가 붙어 있다. 이어서 $M$개 줄에 걸쳐 노선 정보가 입력된다. $a_i$와 $b_i$ ($1 \le a_i < b_i \le N$)는 $i$번째 노선이 연결하는 두 역을 나타낸다. $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$)는 노선을 관리하는 회사를 나타낸다. 어떤 두 역을 연결하는 노선이 두 개 이상 존재하지는 않는다.

다음 줄에는 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} < k_{j, 2} < \cdots < k_{j, l_j} \le K$)가 주어진다. 같은 회사 조합으로 이루어진 1Day 패스포트가 여러 번 입력되지는 않는다.

입력의 끝은 $N=M=H=K=0$인 줄로 나타낸다. 이 데이터는 처리해서는 안 된다.

각 데이터 세트에 대해 계산 결과를 한 줄로 출력하라. 즉 D의 가장 가까운 역에서 라이브 회장의 가장 가까운 역으로 가는 경로가 존재하고 $H$시간 이내에 도달할 수 있으면, 그에 필요한 최소 요금을, 도달할 수 없으면 -1을 출력하라.