Maximizing Profit in Island Reward Retrieval

An ocean contains n islands connected by m undirected stone bridges. Some islands hide attractive rewards with a given temptation value \( k_i \) (set by wzt), and some islands host mercenaries with a base cost \( b_i \) (recruited by lsq). In order to retrieve a reward, lsq must hire a mercenary from a mercenary‐island to travel to a reward‐island.

The cost incurred by a mercenary to travel from his starting island \( i \) to a reward island \( j \) is calculated as follows:

• The mercenary’s base cost \( b_i \).
• The sum of beast counts over every island encountered on the journey (including both the starting island and the destination island).
• The sum of the lengths of all bridges crossed.

That is, if a mercenary from island \( i \) travels along a path \( i = v_0, v_1, \dots, v_\ell = j \), then his total cost is

[ \text{cost}(i,j)= b_i + \sum_{r=0}^{\ell} \text{beasts}(v_r) + \sum_{r=1}^{\ell} d(v_{r-1},v_r). ]

Each mercenary can be used only once, and each reward must be retrieved by hiring exactly one (distinct) mercenary. lsq's net profit is defined as the sum of all rewards' temptation values minus the total cost paid for hiring the mercenaries. Formally, if you assign a mercenary to each reward such that the reward at island \( j \) is retrieved with cost \( c(i,j) \), the profit is

[ \text{Profit} = \sum_{j \ in \ R} k_j - \sum_{j \ in \ R} c(i,j). ]

Your task is to help lsq make the best assignment so that all rewards are retrieved and the overall profit is maximized. If there is any reward that is unreachable from any available mercenary, output -1.

Input/Output Formats: See below.

inputFormat

The input begins with:

 n m

where \( n \) is the number of islands and \( m \) is the number of bridges. Then there are \( m \) lines, each containing three integers:

 u v d

denoting a bidirectional bridge connecting islands \( u \) and \( v \) with length \( d \).

The following line contains \( n \) integers representing the number of beasts on each island from island 1 to island \( n \).

Next, a line with an integer \( r \) is given, specifying the number of reward islands. The following \( r \) lines each contain two integers:

 index k

denoting that island index has a reward with temptation value \( k \). (If an island does not have a reward, it will not appear here.)

Then, a line with an integer \( p \) is given, indicating the number of mercenary islands. The next \( p \) lines each contain two integers:

 index b

meaning that island index has a mercenary available with a base cost \( b \). (If an island does not have a mercenary, it will not appear here.)

You may assume that islands are numbered from 1 to \( n \) and that the bridges are bidirectional.

outputFormat

Output a single integer: the maximum profit lsq can obtain by optimally assigning mercenaries to rewards. If it is impossible for all rewards to be retrieved, output -1.

sample

3 2
1 2 2
2 3 3
1 2 3
1
3 100
2
1 10
2 20

79