Fastest Game Completion

gcd is playing an interesting game that is abstracted as a graph with \(n\) nodes. In the game there are \(m\) treasures distributed on the graph. Each treasure \(i\) is located at a node and can be obtained only when all the treasures in its prerequisite set \(S_i\) (given as indices) have been collected.

gcd also possesses a magical artifact that allows him to teleport. The artifact can be used \(k\) times initially. Additionally, when the prerequisites for a treasure are fulfilled the moment the achievement is reached, a bonus number of teleports is awarded. When a treasure \(i\) is collected, its associated bonus is added to the current teleport count.

You start at node 1, and the game is completed when all treasures have been collected. You can either travel between nodes or use a teleport (if available). Walking between nodes from node \(u\) to \(v\) takes a given time cost \(d_{uv}\) (provided in an \(n \times n\) matrix). Teleporting takes 0 time but reduces the current teleport count by 1.

Your task is to determine the minimum total time required to complete the game.

Note: When you collect a treasure, if you are already at its location, you can obtain it immediately with no extra travel time. Also, upon collecting a treasure, the teleport bonus is added to your available teleports immediately.

inputFormat

The input begins with three integers \(n, m, k\) where \(n\) is the number of nodes, \(m\) is the number of treasures, and \(k\) is the initial number of teleports available.

This is followed by an \(n \times n\) matrix where the \(j\)th number in the \(i\)th row denotes the walking time \(d_{ij}\) from node \(i\) to node \(j\). It is guaranteed that \(d_{ii} = 0\) for all \(i\).

Then, \(m\) lines follow, each describing a treasure. The \(i\)th treasure is described by:

• An integer pos (1-indexed) representing the location of the treasure.
• An integer bonus which is the number of teleports rewarded upon collecting this treasure.
• An integer \(r\) denoting the number of prerequisites followed by \(r\) integers denoting the indices (1-indexed) of the treasures that must be collected before treasure \(i\) can be obtained.

You start at node 1. It is guaranteed that the prerequisites for each treasure form a valid dependency.

outputFormat

Output a single integer, the minimum total time required to collect all treasures.

sample

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

1