Minimum Development Cost for Cargo Transportation

You are given several sources of cargo and several transit islands. The standard cargo must be transported from their originating source to the military base at the war‐front. There are also some special cargo sources carrying private cargo which are automatically delivered (i.e. they do not obey the capacity and shipping restrictions described below). The transportation network has the following properties and rules:

1. There are n standard cargo sources. The i-th source provides a given amount of cargo.
2. There are m transit islands. Each island is split into two parts: an input part and an output part. An island can store at most \(w\) units of standard cargo at any time. The split is used to enforce this capacity.
3. Each island is allowed to receive cargo only from a certain subset of standard cargo sources. In other words, for each island, a list of allowed source indices is provided. (Special cargo are exempt from this restriction.)
4. Cargo is transported in shipments. Every shipment between two nodes (either from a source to an island or between two islands) is limited to at most \(d\) units and for each pair (sender, receiver) at most one shipment is allowed.
5. Cargo from standard sources must be eventually forwarded to the military base. However, only a designated subset of islands is allowed to deliver cargo directly to the base; for each such island the shipment capacity to the base is also limited to \(d\) units.
6. The islands are interconnected by e bidirectional sea routes. Each route connects two islands and has an associated cost \(v\). For any two islands, define \(K\) as the length of the shortest path (in terms of the sum of \(v\) values) between them. In the cargo network, if an island i ships cargo to island j, then it is required that \(K\le V\), where \(V\) is a global threshold. That is, you are allowed to use a shipment between islands i and j only if the shortest distance between them (computed over all islands) does not exceed \(V\).
7. The development cost of the entire shipping network is defined as the maximum \(K\) value among all island-to-island shipments used. Your task is to choose the smallest possible \(V\) such that, by only allowing shipments between islands with \(K\le V\), all the standard cargo can be delivered to the military base obeying the above rules.

Input and Output Protocol

The problem is to compute the minimum \(V\) which enables a valid transportation plan for all standard cargo. (Special cargo is automatically delivered and does not need to be routed.)

Notes on Modeling: You may model the problem as a network flow problem. The network is constructed as follows (note that all shipments from a node to a node have a capacity of at most \(d\)):

• Create a source node S. For each standard cargo source, add an edge from S with capacity equal to the cargo amount at that source.
• For each island i (\(1\le i\le m\)), split it into two nodes: i_in and i_out with an edge from i_in to i_out of capacity \(w\). For each island, for every standard cargo source allowed to send to that island, add an edge from the corresponding cargo source node to i_in with capacity \(d\) (per shipment).
• For any two distinct islands i and j, if the shortest distance between them is \(\le V\), add an edge from i_out to j_in with capacity \(d\). (Shipments between islands are only possible if their shortest distance is at most \(V\).)
• For each island that is allowed to ship cargo directly to the military base, add an edge from its i_out to the sink node T with capacity \(d\).
• After constructing the network (which depends on \(V\)), check if the maximum flow from S to T is at least the total amount of standard cargo. (Remember: special cargo is delivered automatically and does not count.)

Your program should use a binary search over candidate values of \(V\) (drawn from the set of all distinct shortest distances between islands) to find the minimum \(V\) that allows full delivery of the standard cargo.

inputFormat

The input is given as follows:

Line 1: Six integers: n m e w d x
         n: number of standard cargo sources
         m: number of islands
         e: number of bidirectional sea routes
         w: maximum storage capacity of an island (for standard cargo)
         d: maximum shipment amount per delivery between any two nodes
         x: number of special cargo sources (their cargo is automatically delivered)
Line 2: n integers, where the i-th integer represents the cargo amount at the i-th standard source.
Line 3: x integers, where each integer is the cargo amount for a special cargo source (these do not require routing).
The next m lines: Each line describes an island. The line begins with an integer k indicating the number of allowed standard sources for this island, followed by k integers (each between 1 and n) indicating the allowed source indices.
Next line: An integer r followed by r distinct integers in [1, m] indicating the indices of islands that are allowed to ship cargo directly to the military base.
The next e lines: Each line contains three integers: u v v_val, indicating there is a bidirectional sea route between islands u and v with cost v_val.

</p>

outputFormat

Output a single integer, the minimum \(V\) such that all standard cargo can be delivered to the military base under the given rules. If it is impossible, output -1.

sample

2 2 1 10 10 1
5 5
3
1 1
2 1 2
1 2 4

0

</p>