P4923 [MtOI2018] gcd? A Winner in Life!

gcd is a person who loves games.

gcd has recently been playing an interesting game. We abstract this game into a graph with $n$ nodes. gcd needs to find a total of $m$ treasures, which are distributed on the graph. For each treasure, there is a prerequisite set $S$. Only after obtaining all prerequisite treasures can this treasure be obtained. gcd has a divine artifact. This artifact can teleport, and it can be used $k$ times. Each time, it can teleport to any node. In this game, there are also extra achievements. These achievements reward a certain number of teleport uses. An achievement is completed at the instant when the set $S$ is satisfied. Now gcd wants to know the fastest way to clear the game. Please find the minimum time needed to clear it.

The input has a total of $s+m+e+6$ lines. Line $1$ contains $3$ positive integers $n,m,k$. Line $2$ contains $1$ positive integer $s$, the number of achievements. In the next $s$ lines, each line starts with $1$ non-negative integer $num$, meaning how many treasures are required, followed by $num$ integers, which are the IDs of the required treasures. Line $s+3$ contains $s$ positive integers $a_1,a_2,\cdots a_s$, meaning the reward counts of the achievements. Line $s+4$ contains $m$ positive integers $p_1,p_2,\cdots p_m$, meaning the positions of the treasures. Line $s+5$ contains $1$ positive integer $e$, the total number of edges. In the next $e$ lines, each line contains $3$ positive integers $x,y,z$, meaning there is an undirected edge between $x$ and $y$ with weight $z$. In the next $m$ lines, each line starts with $1$ non-negative integer $num$, meaning the number of prerequisites for the treasure, followed by $num$ integers, which are the IDs of the required treasures. The last line contains $1$ positive integer $st$, the starting node.

Output $1$ line with $1$ positive integer: the minimum time.

### Subtasks For $20\%$ of the testdata, $s=0$. For $100\%$ of the testdata, $n\leq 200$, $m\leq 12$, $k\leq 4$, $s\leq 8$, $e\leq 20000$. The sum of all reward counts does not exceed $8$. It is guaranteed that the positions of any two treasures are different. There may be multiple edges. It is guaranteed that a solution exists. ### Source [MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T5 Problem setter: b2019dy 78488 Translated by ChatGPT 5