题目描述

题目译自 XVI OI Olimpiada Informatyczna – III etap Wiedźmak

Bajtazar 成为了一名巫师，专职猎杀怪物。他需穿越一片怪物肆虐的土地，回到故乡拜托城。幸运的是，当地居民世代与怪物抗争，精通打造对抗怪物的专用剑术。这片土地有众多城镇及其间的道路，道路仅在城镇相交，部分道路穿越地下。

作为巫师，Bajtazar 善于收集情报。他了解每条路上可能遭遇的怪物种类及通行时间，也知道哪些城镇有铁匠，以及他们能打造对抗哪些怪物的剑。目前他未持有任何剑，目标是以最短时间抵达拜托城。虽是巫师，他却不知如何规划路线。请帮助他找到一条最快路径，确保在遭遇每种怪物前都能获取对应剑。Bajtazar 体力充沛，可携带任意多把剑。

输入格式

第一行包含四个整数 $n, m, p, k$ $(1 \leq n \leq 200, 0 \leq m \leq 3000, 1 \leq p \leq 13, 0 \leq k \leq n)$，分别表示城镇数、道路数、怪物种类数和铁匠数。城镇编号从 $1$ 到 $n$，其中拜托城为 $n$，Bajtazar 出发地为 $1$。怪物种类编号从 $1$ 到 $p$。

接下来的 $k$ 行描述铁匠，每行一个。第 $i+1$ 行包含整数 $w_i, q_i, r_{i,1} < r_{i,2} < \ldots < r_{i,q_i}$ $(1 \leq w_i \leq n, 1 \leq q_i \leq p, 1 \leq r_{i,j} \leq p)$，分别表示铁匠所在城镇编号、能打造的怪物种类数及其种类（升序）。铁匠可居于同一城镇。

接下来的 $m$ 行描述道路。第 $k+i+1$ 行包含整数 $v_i, w_i, t_i, s_i, u_{i,1} < u_{i,2} < \ldots < u_{i,s_i}$ $(1 \leq v_i < w_i \leq n, 1 \leq t_i \leq 500, 0 \leq s_i \leq p, 1 \leq u_{i,j} \leq p)$，分别表示道路连接的城镇、通行时间（双向相同）、路上可能遇到的怪物种类数及其种类（升序）。任意两城镇间最多一条道路。

输出格式

输出一个整数，表示到达拜托城的最短总时间。若无法到达，输出 $-1$。

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

24

图中圆圈表示城镇，内部数字为编号。边表示道路，上方数字为通行时间。圆圈旁斜体数字表示铁匠能打造的怪物对抗剑种类。边下方斜体数字表示路上可能遇到的怪物种类。

Bajtazar 应先前往城镇 $2$，获取对抗怪物 $2$ 的剑，返回城镇 $1$，再前往城镇 $4$，最后到达拜托城（$6$）。总时间：$2 + 2 + 2 + 18 = 24$。

2 1 1 1
2 1 1
1 2 1 1 1

-1

Bajtazar 无法获取对抗怪物 $1$ 的剑，因此不能到达拜托城。