Problem 1674. -- 冒险岛

1674: 冒险岛

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

不知道怎么的,nc准备玩冒险岛了.他决定玩强大帅气唤灵斗师(当然没有nc本人帅).辛辛苦苦,欢欢乐乐,他终于可以转职了.但是想转职并没有那么容易,因为他还是矮丑穷挫的新手,并不是强大的唤灵!!! 
具体来说,这里有n个城镇,之间有m条双向道路,通过每条路需要一定的时间.因为这个冒险岛有点奇怪,怪物全部都集中在道路上.一共也只有p种怪物.这些怪物非常强,就nc一个新手是打不过的.于是他要在城镇中拿属性相克的武器去打.因为城镇并不是商业中心,每个城镇也只有特定的几种武器. 现在nc想知道, 从1号点到n号点的最短时间.

Input

第一行包含四个整数, n,m,p,k. 分别表示城镇数量, 道路数量, 怪物数量和有k条关于武器的信息. 
接下来k行, 每行有若干个整数, wi,qi,ri,1..ri,qi. Wi表示城镇编号, qi表示编号为wi的城镇可以卖的武器数量. 接着是qi个数, 分别表示该武器可以克的怪物的编号. 保证编号单调递增. 
接下来m行, 每行有4个整数, s,t,v,w.分别表示有一条道路连结s和t, 通过需要的时间为v, 这条道路上怪物的种类为w. 接着是w个数, 表示这个道路上怪物的编号. 保证编号单调递增. 两个点之间没有多条道路直接相连.

Output

输出从1到n的最短时间. 如果不能到达, 输出-1.

Sample Input

6 7 4 2
2 1 2
3 2 1 3
1 2 2 0
2 3 9 0
1 4 2 1 2
2 5 3 0
4 5 5 2 2 3
4 6 18 0
5 6 3 2 1 2

Sample Output

24

HINT

Source

[Submit][Status]