题目背景

gcd 是一个热爱游戏的人。

题目描述

gcd 最近在玩一个有趣的游戏。

我们把这个游戏抽象成一张图，图上有 $n$ 个点，gcd 需要寻找总计 $m$ 件宝物，它们分布在图上。

对于每件宝物而言，将会有一个前置集合 $S$。只有当取得所有前置宝物时，才能获得该宝物。

gcd 拥有一件神器，这件神器具有传送功能，它可以使用 $k$ 次，可以传送到一个任意节点。

对于游戏而言，肯定会有额外的成就，这些成就会奖励一定的传送次数，成就的达成是满足集合 $S$ 的一瞬间。

现在 gcd 想知道能最快通关的方法，请你求出通关的最少时间。

输入格式

输入共 $s+m+e+6$ 行。

第 $1$ 行输入 $3$ 个正整数 $n,m,k$。

第 $2$ 行输入 $1$ 个正整数 $s$ 表示成就的数量。

以下 $s$ 行每行输入 $1$ 个非负整数 $num$ 表示需求多少个宝物，然后输入 $num$ 个数，为所需宝物编号。

第 $s+3$ 行输入 $s$ 个正整数 $a_1,a_2,\cdots a_s$ 表示成就的奖励次数。

第 $s+4$ 行输入 $m$ 个正整数 $p_1,p_2,\cdots p_m$ 表示宝物的位置。

第 $s+5$ 行输入 $1$ 个正整数 $e$ 表示边的总数。

以下 $e$ 行每行输入 $3$ 个正整数 $x,y,z$ 表示 $x$ 与 $y$ 之间有一条边权为 $z$ 的无向边连接。

以下 $m$ 行每行输入 $1$ 个非负整数 $num$ 表示宝物前置要求个数，然后输入 $num$ 个数，为要求的编号。

最后一行输入 $1$ 个正整数 $st$ 表示起点。

输出格式

输出共 $1$ 行 $1$ 个正整数，输出最少时间。

3 2 0
1
1 1
1
2 3
3
1 2 20
1 3 20
3 2 1
0
0
1

20

3 2 0
1
1 1
1
2 3
3
1 2 1
1 3 20
3 2 20
1 2
0
1

40

提示

子任务

对于 $20\%$ 的数据，$s=0$。

对于 $100\%$ 的数据，$n\leq 200$，$m\leq 12$，$k\leq 4$，$s\leq 8$，$e\leq 20000$ ，奖励次数总和不超过 $8$，保证每两个宝物的位置不相同，可能有重边，保证有解。

题目来源

MtOI2018 迷途の家の水题大赛 T5

出题人：b2019dy

78488