Description

Xiao M opened two huge farmlands $A$ and $B$ in MC (you can assume their capacity is infinite). Now, Xiao P has seeds of $n$ crop types, exactly $1$ seed for each type (i.e., you can plant at most one plant of each type), numbered from $1$ to $n$.

For the $i$-th crop, planting it in $A$ yields a profit of $a_i$, and planting it in $B$ yields a profit of $b_i$. There is also a special phenomenon: certain sets of crops planted together on the same field yield an extra profit. Xiao M found $m$ such crop combinations in total. For the $i$-th combination, if all its crops are planted together in $A$, you gain an extra $c_{1,i}$ profit; if they are planted together in $B$, you gain an extra $c_{2,i}$ profit.

Xiao M quickly computed the maximum profit, but he wants to test you. Can you answer this question?

Input Format

The first line contains an integer $n$, the number of crop types.

The second line contains $n$ integers, representing $a_i$.

The third line contains $n$ integers, representing $b_i$.

The fourth line contains an integer $m$, the number of combinations.

Each of the next $m$ lines describes one combination: on the $i$-th line, the first integer $k_i$ is the number of crops in the $i$-th combination, followed by two integers $c_{1,i}, c_{2,i}$, then $k_i$ integers indicating the indices of the crops in this combination.

Output Format

Output a single line containing one integer, the maximum profit.

3
4 2 1
2 3 2
1
2 3 2 1 2

11

Hint

Sample Explanation:

Plant crops $1, 2$ in field $A$, and crop $3$ in field $B$. Profit: $4+2+3+2=11$.

Constraints:

For $100\%$ of the testdata, $1 \le k_i < n \le 10^3$, $1 \le m \le 10^3$. All values that appear in the problem are non-negative integers not exceeding $1000$.

Translated by ChatGPT 5