[MtOI2018] gcd?人生赢家!

题目背景

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$ 个正整数,输出最少时间。

输入输出样例

输入样例 #1

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

输出样例 #1

20

输入样例 #2

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

输出样例 #2

40

说明

### 子任务 对于 $20\%$ 的数据,$s=0$。 对于 $100\%$ 的数据,$n\leq 200$,$m\leq 12$,$k\leq 4$,$s\leq 8$,$e\leq 20000$ ,奖励次数总和不超过 $8$,保证每两个宝物的位置不相同,可能有重边,保证有解。 ### 题目来源 [MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T5 出题人:b2019dy 78488