Delivery Fleet Optimization

You are given a network of intersections and bidirectional roads. Each road connects two intersections and has an associated travel distance. A delivery company owns a fleet of trucks, where each truck has a capacity which is the maximum number of delivery tasks (visits to intersections) it can handle on a single trip. The company has several delivery orders, each requiring a certain number of visits at a specified intersection.

The task is to determine if the trucks can complete all the deliveries under the given capacity constraints, and if so, compute the minimum total travel distance across all trucks. Each truck can start at any intersection, perform its assigned deliveries in the given order, and then return to its starting point. The travel distance for a truck is the sum of the shortest distances between consecutive stops (including from the starting point to the first delivery and from the last delivery back to the start).

If it is impossible to complete all deliveries without exceeding the capacities, output -1.

Note: For any formulas, we use LaTeX format. For instance, the capacity constraint is \(\sum_{i=1}^{l} p_i \le \sum_{j=1}^{k} c_j\), where \(p_i\) is the number of deliveries required at intersection \(i\) and \(c_j\) is the capacity of truck \(j\).

inputFormat

The input is given via standard input (stdin) and has the following format:

Line 1: Two integers (n) and (m) representing the number of intersections and the number of roads, respectively.

The next (m) lines: Each line contains three integers (u), (v), and (d), indicating there is a bidirectional road between intersections (u) and (v) with distance (d).

The next line: An integer (k) representing the number of trucks.

The following line: (k) integers, where each integer is the capacity of a truck.

Next line: An integer (l) representing the number of deliveries.

The next (l) lines: Each contains two integers (i) and (p) where (i) is the intersection and (p) is the number of deliveries required at that intersection.

outputFormat

Output a single integer to standard output (stdout): the minimum total travel distance required to complete all deliveries while respecting truck capacities, or (-1) if it is not possible.## sample

5 6
1 2 3
1 3 4
1 4 2
2 4 5
3 4 1
4 5 6
3
2 2 4
3
1 5
3 3
5 1

-1