Minimum Time to Destroy All Giant Robots

In the year \(3333\), on a planet in the galaxy, the X Legion and the Y Legion are engaged in a fierce battle. At one stage, the Y Legion deploys \(N\) giant robots to attack the X Legion. The \(i\)-th robot has an armor value of \(A_i\). A robot is destroyed once its armor is reduced to 0 or below.

The X Legion uses \(M\) laser weapons. The \(i\)-th laser deals damage continuously at a rate of \(B_i\) per second to whichever robot it is targeting. However, each laser weapon is very peculiar—it can only target a specific subset of robots. For each laser weapon, you are given the list of robots it can attack.

Your task is to determine the minimum time \(T\) required for the X Legion to destroy all of the Y Legion's giant robots, assuming that the lasers can split their attack time arbitrarily among the robots they can target.

Mathematical Formulation:

For each laser \(i\), in time \(T\) it can deliver a total damage of \(T \times B_i\). If a laser \(i\) attacks robot \(j\) for \(f_{ij}\) seconds (with \(j\) belonging to the set of robots that laser \(i\) can attack), then robot \(j\) receives \(B_i \times f_{ij}\) damage from laser \(i\). We need to find the smallest \(T\) such that there exist nonnegative numbers \(f_{ij}\) satisfying:

[ \begin{aligned} \sum_{j \in S_i} f_{ij} &\le T \quad &\text{for each laser } i,\ \sum_{i: j \in S_i} B_i f_{ij} &\ge A_j \quad &\text{for each robot } j. \end{aligned} ]

This can be modeled as a flow problem. Construct a flow network with a source connected to each laser node \(i\) with capacity \(T \times B_i\), and from each laser node \(i\) you add edges to every robot \(j\) that laser can target (with infinite capacity). Each robot node \(j\) is connected to the sink with capacity \(A_j\). The minimum \(T\) is the smallest value for which the maximum flow equals \(\sum_{j=1}^N A_j\).

inputFormat

The input begins with two integers \(N\) and \(M\) representing the number of giant robots and the number of laser weapons, respectively.

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\) representing the armor values of the robots.

The third line contains \(M\) integers \(B_1, B_2, \dots, B_M\) representing the damage rate per second of each laser.

Then \(M\) lines follow. The \(i\)-th of these lines starts with an integer \(k_i\), the number of robots that the \(i\)-th laser can target, followed by \(k_i\) distinct integers which are the 1-indexed indices of these robots.

outputFormat

Output the minimum time \(T\) required to destroy all the giant robots. The answer should be printed as a floating-point number with at least 6 digits after the decimal point.

sample

2 2
10 20
5 5
1 1
1 2

4.000000