Fireworks Display Optimization

Iratis wants to light some fireworks outdoors. Each firework has its own inherent beauty value. However, there are two kinds of relationships between fireworks:

• Relation One: For each firework \(x\), there is an associated firework \(a_x\). If both \(x\) and \(a_x\) are lit, the beauty of \(x\) decreases by \(b_x\).
• Relation Two (Series Constraint): Some fireworks belong to a series and must be lit together. In each series exactly one firework is designated as the main firework and every firework belongs to at most one series.

There is one more twist. Suppose a series \(S_1\) has main firework \(p_1\). If the firework corresponding to \(p_1\) in Relation One (i.e. \(a_{p_1}\)) belongs to another series \(S_2\), then for every other firework \(x\) in \(S_1\) (i.e. \(x\neq p_1\)) the Relation One between \(x\) and \(a_x\) will not lower \(x\)’s beauty if \(a_x\) does not lie in \(S_1\) or \(S_2\). (Otherwise, if both \(x\) and \(a_x\) are lit, \(x\)’s beauty is reduced by \(b_x\).)

Iratis has \(n\) fireworks in total. For each firework \(x\) (indexed from 1 to \(n\)), its inherent beauty is given, and for Relation One, the associated firework is \(a_x\) and the penalty is \(b_x\) if both are lit (subject to the exemption described above). Additionally, there are \(m\) series; for each series, you are given the indices of the fireworks in that series (the first one is the main firework), and if any firework in a series is lit then all fireworks in that series must be lit.

Your task is to choose a subset of fireworks to light (while respecting the series constraint) such that the total beauty of the lit fireworks is maximized. The total beauty is the sum of the inherent beauties minus any penalties incurred from Relation One.

Input/Output formats are described below.

inputFormat

The input begins with two integers \(n\) and \(m\) \((1 \leq n \leq 20)\) --- the number of fireworks and the number of series respectively.

The next line contains \(n\) integers, where the \(i\)th integer represents the inherent beauty \(v_i\) of firework \(i\).

Then follow \(n\) lines. The \(i\)th of these lines contains two integers \(a_i\) and \(b_i\) \((1 \leq a_i \leq n)\), meaning that if firework \(i\) and firework \(a_i\) are lit then the beauty of firework \(i\) will be reduced by \(b_i\) (unless an exemption applies as described above).

Then follow \(m\) lines describing the series. Each series description starts with an integer \(k\) (the number of fireworks in that series), followed by \(k\) distinct integers, which are the 1-indexed IDs of the fireworks in that series. The first ID is the main firework of the series.

You may assume that each firework belongs to at most one series. It is allowed that \(m=0\), meaning no series exist.

outputFormat

Output a single integer: the maximum total beauty achievable.

sample

5 1
10 20 30 40 50
3 5
1 3
5 7
5 6
2 2
3 2 4 5

100