Magical Brewing

In this problem, Youyou (幽香) wants to brew and store as much wine as possible to satisfy the demand. There are n brewing points numbered from 1 to n and m storage points numbered from 1 to m. A brewing point i can produce any nonnegative real amount x (up to a cap of c_i) at the cost of \(a_i x^2+b_i x\) units of magic. Some pairs of brewing point and storage point are connected by channels; if there is a channel from brewing point i to storage point j, then the wine produced at i can be transported to j without extra cost. Each storage point j can store at most d_j liters of wine.

Under the given network constraints, Youyou wants to store as much wine as possible. Among all ways to achieve the maximum storage, she wishes to minimize the total magic cost. Help her compute the minimum magic required.

Notes:

• The cost function at brewing point i is \(a_i x^2 + b_i x\). Here \(x\) can be any nonnegative real number up to \(c_i\).
• A channel exists only from a brewing point to a storage point. There is no cost for transporting the wine.
• The maximum wine stored is determined by both the brewing limits and the storage capacities reachable via the network channels.

Mathematical formulation:

Let \(x_i\) be the amount produced at brewing point \(i\) (with \(0 \le x_i \le c_i\)) and let the production be assigned to storage points according to the channels such that for each storage point \(j\) the total incoming wine does not exceed \(d_j\). The feasibility condition is equivalent to a flow constraint in a bipartite graph. The maximum storable wine is given by the maximum flow \(F\) from the brewing nodes to the storage nodes. Then the problem becomes:

[ \text{Minimize } \sum_{i=1}^{n} \left(a_i x_i^2+b_i x_i\right) \quad \text{subject to } \sum_{i=1}^{n} x_i = F, ; 0 \le x_i \le c_i \text{ for } i=1,\ldots,n ]

Since the cost functions are convex the optimum can be obtained by equating the marginal costs on the points that are not at their bounds. One common approach is to use a binary search on a dual variable \(\lambda\) such that for each brewing point \(i\) one sets

[ x_i = \min\Bigl{ c_i, \max\Bigl{0, \frac{\lambda-b_i}{2a_i}\Bigr}\Bigr}, ]

and \(\lambda\) is chosen so that \(\sum_{i=1}^n x_i = F\). The total cost is then \(\sum_{i=1}^n \left(a_i x_i^2+b_i x_i\right)\). In this problem, you are asked to compute that minimum cost.

inputFormat

The input begins with two integers n and m (\(1 \le n,m \le 200\)), representing the number of brewing points and storage points respectively.

Then follow n lines, each containing three numbers: a_i, b_i, and c_i (all positive, with \(c_i\) representing the maximum amount that can be produced at brewing point \(i\)).

The next line contains m integers: d₁, d₂, ..., d_m, where \(d_j\) is the capacity of storage point j.

The next line contains an integer k representing the number of channels.

Each of the following k lines contains two integers i and j (1-indexed) indicating that there is a channel from brewing point i to storage point j.

You may assume that channels are unidirectional (from brewing to storage) and that there are no duplicate channels.

outputFormat

Output a single number, which is the minimum magic required to produce and transport the maximum amount of wine. The answer is considered correct if it is within an absolute or relative error of \(10^{-6}\).

sample

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

71.000000