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} < \dots < 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} < \dots < 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。

样例

输入 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

输出 1

24

输入 2

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

输出 2

-1

说明

图中的圆盘代表城镇；圆盘内的数字是城镇编号。边代表道路；边上方的数字是走完该道路所需的时间。圆盘旁边的数字（斜体）表示该城镇铁匠制造的宝剑所能克制的怪物种类。边下方的数字（斜体）表示在道路上可能遇到的怪物种类。

猎魔人 Byteasar 应该先前往 2 号城镇，获取一把克制 2 号怪物的宝剑，回到 1 号城镇，然后前往 4 号城镇，最后从那里前往 Byteburg。

在第二个样例中，Byteasar 无法获得克制 1 号怪物的宝剑，这使得他无法到达 Byteburg。