Problem Description

Tokyo 7th Sisters is an idol training card & rhythm adventure game playable on iPhone and Android. You are thinking about a simplified version of some of its specifications.

In this simplified version of the game, you can select 9 different idols from multiple ones to form a unit, which allows you to play rhythm games or stage battles. The base ability value of the unit used in the game is determined by the sum of the ability values of the selected idols.

Additionally, the game has a combo system where you can obtain a combo bonus by fulfilling the combo conditions. If there are at least 3 members in the formed unit who meet the specified conditions for a combo, you can obtain the bonus for that combo. For each combo, it is known in advance which idols meet the specified conditions.

The final ability value of the unit is the sum of the unit's base ability value and all obtained combo bonuses.

You want to combine idols to maximize the final ability value of the unit. Please find the maximum final ability value.

Note that the unit combinations and combos in this problem are simplified specifications and may differ slightly from the specifications of Tokyo 7th Sisters.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ A_2 $ ... $ A_N $ $ B_1 $ $ C_1 $ $ I_{1,1} $ $ I_{1,2} $ ... $ I_{1,C_1} $ $ B_2 $ $ C_2 $ $ I_{2,1} $ $ I_{2,2} $ ... $ I_{2,C_2} $ : $ B_M $ $ C_M $ $ I_{M,1} $ $ I_{M,2} $ ... $ I_{M,C_M} $

• The first line contains the number of selectable idols $N\ (9≦N≦16)$ and the number of combos that can be triggered using only the selectable idols $M\ (0≦M≦50)$, separated by spaces.
• The second line contains $ N $ integers separated by spaces, where the $ i $-th integer represents the base ability value of the $ i $-th idol $ A_i(1≦A_i≦10,000) $.
• The next $ M $ lines contain information about each combo. The $i\ (1≦i≦M)$-th line contains the information for the $ i $-th combo separated by spaces. The information consists of several integers, where the first integer is the combo bonus for the $ i $-th combo $ B_i(1≦B_i≦10,000) $. The second integer is the number of idols who meet the combo's conditions $ C_i(3≦C_i≦N) $. The following integers, where the $j\ (1≦j≦C_i)$-th integer represents the index of the idol who meets the condition $ I_{i,j}(1≦I_{i,j}≦N) $. At this time, if $ j≠k $, then $I_{i,j}\ ≠\ I_{i,k}$ is satisfied.

Output Format

Output the maximum final ability value of the unit in one line.

End the output with a newline.

Sample Input and Output

Sample Input #1

10 1
100 200 300 400 500 600 700 800 900 1000
1000 3 1 2 3

Sample Output #1

6100

Sample Input #2

12 10
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 4 1 2 4 7
1000 4 1 9 11 12
1000 4 3 5 8 9
1000 4 6 10 11 12
1000 4 2 4 7 10
1000 4 1 8 9 10
1000 3 1 9 12
1000 4 3 8 11 12
1000 4 1 2 3 4
1000 4 7 8 9 10

Sample Output #2

19000

Sample Input #3

13 8
328 781 104 102 132 108 100 102 104 108 168 102 100
184 4 10 11 3 4
190 4 9 6 2 5
282 6 9 1 3 12 10 8
205 8 13 10 1 12 7 2 8 11
122 8 13 5 4 3 8 9 12 10
112 7 11 6 12 8 2 13 5
102 4 4 13 6 12
109 6 7 2 13 1 8 6

Sample Output #3

3239

Notes/Hints

Sample Explanation 1

Selecting the idols from the 1st to the 3rd and from the 5th to the 10th to form a unit results in a base ability value of 5100 and a combo bonus of 1000, making the final ability value 6100.

Sample Explanation 2

The base ability value is always 9000. As an example, selecting the idols 1, 2, 4, 5, 8, 9, 10, 11, and 12 to form a unit allows you to obtain all combo bonuses.

见题面 Input 部分

见题面 Output 部分