You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Byteasar 成为了一名猎魔人——一个征服怪物的人。

目前他要返回他的家乡 Byteburg。可惜回家的路要经过一个充满野兽的土地。幸运的是，当地居民被迫与怪物斗争了几个世纪，已经掌握了锻造的艺术——他们现在能够制造出对抗野兽非常有效的特殊剑。

Byteasar 所经过的土地相当广阔：那里有许多城镇，许多道路连接着它们。

这些道路不会在城镇外交叉（主要是因为其中一些是地下通道）。

Byteasar 已经收集了关于这片土地的所有实用信息（所有猎魔人都喜欢知道这些事情）。

他知道在每条路上可能遇到的怪物种类，以及他需要多少时间才能走完这条路。

他还知道在哪些村庄有铁匠，以及他们制作的剑对哪些种类的怪物有效。

Byteasar 想尽快回到 Byteburg。

作为一个猎魔人，他对自己不知道最佳路线感到相当羞愧，而且他目前身上没有剑。

帮助他找到到 Byteburg 的最短路径，以便每当他可能遇到某种怪物时，他之前就有机会获得一把合适的剑来对抗野兽。

你不需要担心剑的数量或重量——每个猎魔人都像牛一样强壮，所以他可以携带（几乎）无限数量的装备，特别是剑。

输入格式

标准输入的第一行包含四个整数：$n,m,p,k$ ($1\le n\le 200,0\le m\le 3000,1\le p\le 13,0\le k\le n$)，它们分别表示：

城镇的数量，连接它们的道路数量，不同种类的怪物数量和铁匠的数量。

城镇从 $1$ 到 $n$ 编号，其中 $n$ 是 Byteburg 的编号，$1$ 是 Byteasar 开始的村庄编号。怪物种类从 $1$ 到 $p$ 编号。

接下来的 $k$ 行给出了连续铁匠的资料，每行一个。第 $(i+1)$ 行包含整数 $w_i,q_i,r_{i,1}<r_{i,2}<...<r_{i,q_i}$ ($1\le w_i\le n,1\le q_i\le p,1\le r_{i,j}\le p$)，它们分别表示：铁匠所在的城镇编号，他的剑对抗的不同种类怪物的数量，以及怪物种类本身（按升序排列）。注意，一个城镇可能有多个铁匠。

然后是 $m$ 行道路的描述。第 $(k+i+1)$ 行包含整数 $v_i,w_i,t_i,s_i,u_{i,1}<u_{i,2}<...<u_{i,s_i}$ ($1\le v_i<w_i\le n,1\le t_i\le 500,0\le s_i\le p,1\le u_{i,j}\le p$)，它们分别表示：道路连接的城镇，走完这条路所需的时间（两个方向相同），这条路上可能出现的不同种类怪物的数量，最后是怪物种类本身（按升序排列）。没有两条道路连接同一对城镇。

输出格式

你的程序应输出一个整数到标准输出——到达 Byteburg 所需的最短总时间。

如果无法到达 Byteburg，则该数字应为 $-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