Problem Background

gcd is an avid gamer.

Problem Description

gcd has recently been playing an interesting game.

We abstract this game into a graph with $n$ nodes, where gcd needs to find a total of $m$ treasures distributed across the graph.

For each treasure, there will be a prerequisite set $S$. Only when all the prerequisite treasures are obtained can this treasure be acquired.

gcd possesses a magical artifact with teleportation capabilities, which can be used $k$ times to teleport to any node.

In the game, there are additional achievements that reward additional teleportation uses. These achievements are granted the moment the set $S$ is satisfied.

Now, gcd wants to know the fastest way to complete the game. Please calculate the minimum time required to complete the game.

Input Format

The input consists of $s+m+e+6$ lines.

The first line contains three positive integers $n, m, k$.

The second line contains one positive integer $s$ representing the number of achievements.

The next $s$ lines each contain one non-negative integer $num$ indicating how many treasures are required, followed by $num$ numbers, which are the required treasure IDs.

The $s+3$ line contains $s$ positive integers $a_1, a_2, \cdots a_s$ representing the reward times for the achievements.

The $s+4$ line contains $m$ positive integers $p_1, p_2, \cdots p_m$ representing the positions of the treasures.

The $s+5$ line contains one positive integer $e$ representing the total number of edges.

The next $e$ lines each contain three positive integers $x, y, z$ indicating that there is an undirected edge with weight $z$ connecting nodes $x$ and $y$.

The next $m$ lines each contain one non-negative integer $num$ indicating the number of prerequisite treasures required, followed by $num$ numbers, which are the required IDs.

The last line contains one positive integer $st$ representing the starting point.

Output Format

The output consists of one line with one positive integer, which is the minimum time required.

Sample Input and Output

Input Sample #1

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

Output Sample #1

20

Input Sample #2

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

Output Sample #2

40

Notes

Subtasks

For $20\%$ of the data, $s=0$.

For $100\%$ of the data, $n \leq 200$, $m \leq 12$, $k \leq 4$, $s \leq 8$, $e \leq 20000$, the total reward times do not exceed $8$, each pair of treasure positions are unique, there may be duplicate edges, and a solution is guaranteed.

Problem Source

MtOI2018 Lost Home Water Problem Contest T5

Problem Author: b2019dy

78488

见题面 Input 部分

见题面 Output 部分