Background

gcd is a person who loves games.

Problem Description

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.

Input Format

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 Format

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

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

Hint

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 迷途の家の水题大赛 T5

Problem setter: b2019dy

78488

Translated by ChatGPT 5