题面翻译

大陆上有 $n$ 个村庄，$m$ 条双向道路，$p$ 种怪物，$k$ 个铁匠，每个铁匠会居住在一个村庄里，你到了那个村庄后可以让他给你打造剑，每个铁匠打造的剑都可以对付一些特定种类的怪物。

每条道路上都可能出现一些特定种类的怪物，每条道路都有一个通过所需要的时间，现在要从 $1$ 走到 $n$，初始的时候你没有剑，要求在经过一条道路的时候，对于任意一种可能出现在这条道路上的的怪物，你都有已经有至少一把剑可以对付他，求从$1$ 走到 $n$ 的最短时间（打造剑不需要时间）

题目描述

拜特萨是一个英雄。 目前，他将返回家乡字节堡。唉，回家的路要穿过一片到处都是野兽的土地。幸运的是，被迫与怪物战斗了几个世纪的居民已经掌握了铁匠的艺术——他们现在能够制造出非常有效的特殊剑来对付野兽。 拜特萨漫游的土地相当广阔：那里有许多城镇，许多道路将它们连接起来。 这些道路不会在城镇外穿过（主要是因为其中一些是地下通道）。 拜特萨收集了关于这片土地的所有实用信息（所有人都想知道这些事情）。 他知道自己可能会在每条路上遇到什么样的怪物，也知道自己需要多少时间才能走下去。 他还知道哪些村庄有铁匠，他们制造的剑能对付什么样的怪物。 拜特萨希望尽快回到字节堡。 作为一英雄，他感到非常羞愧，因为他不知道最好的路线，而且他现在身上没有剑。 帮助他找到通往字节堡的最短路径，而且，在他遇到怪物的时候，需要保证恰好有杀死这个怪物的剑。 你不必担心剑的数量或重量——每个英雄都像牛一样强壮，所以他可以携带无限数量的装备，尤其是剑。

输入格式

输入的第一行包含四个整数：$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$是拜特萨的家乡字节堡，$1$是拜特萨开始的村庄的数字。

在接下来的k行里，每行包括若干个数，其中第一个数x($1 \le x \le n$)为铁匠所在的城镇，第二个数为该铁匠能铸造的剑的数量x($1 \le x \le p$)，后面的x个数为没把剑可以消灭的怪兽的编号

在接下来m行里，每行包括若干个数，每一行代表一条路，其中前三个数分别为该路的起点u、终点v、花费时间w($1 \le u,v \le n$),第四个数x($0 \le x \le p$)表示该路段怪物的数量,后面x个数表示怪物的编号

输出格式

输出从起点到终点不被怪兽杀死的前提下的最近距离

样例 #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