WIE-Hexer

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, qi, r{i,1} < r{i,2} < \dots < r{i,q_i}（1 \le w_i \le n，1 \le qi \le p，1 \le r{i,j} \le p$），它们分别表示：铁匠所在的城镇编号，他的剑对抗的不同种类怪物的数量，以及怪物种类本身（按升序排列）。注意，一个城镇可能有多个铁匠。

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

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

如果无法到达 Byteburg，则该数字应为 -1。