# 1 Day Passport

Ԑ : 8 sec, : 131072 KB

### Ԍ

^ɏZޑwD́CIM^XgȂt@ŁC̉ēsSōs郉CuɍsƍlĂD CD͕Ӌ̒nɏZł邽߁Cʔ邱ƂƂĂsD ȂƂނ́CJAGƂgDŔ̔Ău1DaypX|[gv݂̑mD

JAG (Journey Administrative Group) ́CDZލɑ݂邢̓SЂ𓝊gDłD JAǴCSɕ̉wC̊ԂԘH𐮔ĂD eH́CJAGɏЂ̓ꂩ1ЂɂǗĂC2wԂrwőoɌłD ܂eHɂ́Cpۂ̉^ƏvԂ܂Ă (͂ǂɈړꍇł)D JAG̃_C̓VvɍĂCԂ͖0ɉwɔD ܂JAG̊eẃCɂ߂ČfUCĂCH̏芷ɂ鎞Ԃ͖邱ƂłD ړɕKvȌʔ͉^̒PȍvƂȂ.

1DaypX|[ǵCJAǦocE邽߂ɔ̔n߂CpX|[głD JAǴCނ1DaypX|[g̔ĂD epX|[ǵCJAGw肷̔iōw邱ƂłD ܂pX|[gɂ́CJAGɏЖĂC̉ЂǗSĂ̘H1 (ǉ) ɂȂD pX|[ǵCłw邱ƂłC̃pX|[g𕹗p邱ƂłD CpX|[gɏĂȂЂ̊ǗHʂꍇC̘H̉^͒ʏʂKvƂȂD

D́C1DaypX|[g܂gCȂׂCu܂ōsƍlĂD ܂Cނ͏hŗ]vɂ̂Ȃ̂ŁC̍1ł$H$ԈȉŃCu܂ŒH蒅ƍlĂD Cނ͌vZӂł͂Ȃ߁Cw̗FlŃvO~OӂȂȂɏ߂ėD ĂD̂߂ɁĈ悤ȃvOĂ悤D

JAG̘H1DaypX|[g̏񂪗^ꂽƂCD̍Ŋw烉Cu̍ŊwցC$H$Ԉȉňړ邽߂̍ŏp (pX|[gƉ^̍v̍ŏ) ߂vO쐬D $H$ԈȉœBłȂꍇCCu֓BoHȂꍇ́C-1o͂D

### Input

͂́C̃f[^Zbg\C1̓͂Ɋ܂܂f[^Zbg̐150ȉłD ef[^Zbǧ͎̒ʂłD

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

͂͑SĐlŗ^D

܂CJAG̘H񂪗^D $N$ ($2 \le N \le 100$) ͉w̐C$M$ ($1 \le M \le 500$) ͘H̐C$H$ ($1 \le H \le 24$) 1̎ԁC$K$ ($1 \le K \le 8$) JAGɏА\D ewɂ́C$1, 2, \ldots, N$ ƔԍĂD ܂CeЂɂ́C$1, 2, \ldots, K$ ƔԍĂD $M$ sɂ킽ĘH񂪓͂D $a_i$ $b_i$ ($1 \le a_i \lt b_i \le N$) $i$ Ԗڂ̘HȂł2̉w\D $c_i$ ($1 \le c_i \le 10{,}000$) $i$ Ԗڂ̘H̉^C$h_i$ ($1 \le h_i \le H$) ͘H̏vԁC$r_i$ ($1 \le r_i \le K$) ͘HǗĂЂ\D 2̉wԘH2{ȏ㑶݂邱Ƃ͂ȂD

̍sŁCD̍Ŋw $S$ ƁCÃCu̍Ŋw $T$ ^ ($1 \le S, T \le N$)D $S$ $T$ ͈قȂlłD

ɁC1DaypX|[g̏񂪗^D $P$ ($0 \le P \le 2^K - 1$) ́C1DaypX|[g̎ސ\ĂD $P$ sɂ킽āC1DaypX|[g̏񂪓͂D $l_j$ ($1 \le l_j \le K$) $d_j$ ($1 \le d_j \le 10{,}000$) ́Cꂼ $j$ Ԗڂ1DaypX|[gɏĂАƃpX|[g̗\D sɁC$j$ Ԗڂ̃pX|[gɏꂽ $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$) ^D Ђ̑gݍ킹Ȃ1DaypX|[g͂邱Ƃ͂ȂD

͂̏ÍC$N=M=H=K=0$ ̍sɂĕ\D ̃f[^͏sĂ͂ȂȂD

### Output

ef[^Zbgɑ΂āCvZʂ1sŏo͂D Ȃ킿CD̍Ŋw烉Cu̍Ŋwւ̌oH݂ $H$ ԈȓɓBł̂ł΁Ĉ߂̍ŏ̗CH蒅Ȃ̂ł-1o͂D

### 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`

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2014, 2014-07-06
http://acm-icpc.aitea.net/