问题描述

Tokyo 7th Sisters是一款可以在iPhone和Android设备上玩的偶像培养卡牌和节奏冒险游戏。你正在思考这个游戏中的一些简化规则。

在这个简化了一些规则的游戏中，你可以从多个偶像中选择不同的9人组成一个单位，然后进行节奏游戏或舞台战斗。此时，单位的基础能力值由所选偶像的能力值之和决定。

此外，这个游戏还有一个连击（Combo）系统，通过满足连击条件可以获得连击奖励。如果组成的单位满足连击指定的条件的偶像人数超过3人，则可以获得该连击的奖励。对于每个连击，预先知道哪些偶像满足指定的条件。

单位的最终能力值是单位的基础能力值加上获得的所有连击奖励的总和。

你想通过组合偶像来尽可能地提高单位的最终能力值。请计算最终能力值的最大值。

请注意，本问题中的单位组合方式和连击是根据简化规则进行的，与Tokyo 7th Sisters的规则略有不同。

---

输入

从标准输入中按以下格式输入。

$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}$

• 第一行包含两个由空格分隔的整数：你可以选择的偶像数量 $N (9≦N≦16)$ 和能够生成的连击数量 $M (0≦M≦50)$。
• 第二行包含 $N$ 个由空格分隔的整数。其中第 $i$ 个整数表示第 $i$ 个偶像的基础能力值 $A_i(1≦A_i≦10,000)$。
• 第三行到第 $M$ 行描述了每个连击的信息。其中第 $i (1≦i≦M)$ 行包含连击 $i$ 的信息，由空格分隔。连击的信息由多个整数组成，第一个整数是连击奖励的整数 $B_i(1≦B_i≦10,000)$。第二个整数是满足该连击条件的偶像人数 $C_i(3≦C_i≦N)$。随后的整数中第 $j (1≦j≦C_i)$ 个整数表示满足条件的偶像的编号，即整数 $I_{i,j}(1≦I_{i,j}≦N)$。对于任意的 $j≠k$，都有 $I_{i,j} ≠ I_{i,k}$。

---

输出

将单位的最终能力值以一行输出。

输出末尾要包含换行符。

---

示例输入1

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

示例输出1

6100

选择第1到第3个和第5到第10个偶像组成一个单位，基础能力值为5100，连击奖励为1000，并且最终能力值为6100。

---

示例输入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

示例输出2

19000

基础能力值将总是9000。例如，选择第1、2、4、5、8、9、10、11、12个偶像组成一个单位，可以获得所有连击奖励。

---

示例输入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

示例输出3

3239

---