問題文
东京七姐妹是一款可以在iPhone和Android上玩的偶像训练卡牌和节奏冒险游戏。 您正在考虑某些游戏规格的简化版本。
在这个游戏中,一些规格已被简化,您可以从多个偶像中选择不同的偶像。 9 选择人员并选择单位 1 通过将它们配对,您可以玩节奏游戏和舞台战斗。 此时,游戏中使用的单位的基本能力值由所选偶像的能力值总和决定。
另外,这个游戏有一个叫做连击的系统,满足连击条件可以获得连击奖励。 组装的单位有满足组合中指定条件的成员。 3 人数多的话,可以获得该连击的加成。 对于每个组合,我们提前知道哪些偶像会满足指定条件。
单位的最终统计数据是该单位的基本统计数据加上获得的所有组合奖励的总和。
你想要组合偶像来最大化你的单位的最终能力。求最终能力值的最大值。
请注意,本问题中出现的单位组装和组合是简化的规格,可能与东京七姐妹的规格略有不同。
入力
输入是按以下格式从标准输入给出的。
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}
- 1 行显示您可以选择的偶像数量。 N (9≦N≦16) 以及仅使用可选偶像时可以发生的连击数量。 M (0≦M≦50) 用空格分隔。
- 2 行中,N 整数由空格分隔。这几天之一 第 i 个整数是i 第一个偶像的基础能力值 代表 A_i(1≦A_i≦10,000) 。
- 3 从行 M 行提供有关每个组合的信息。其中 i (1≦i≦M) 在线 有关第 i 个组合的信息以空格分隔。组合信息由多个整数组成,1 第二个整数是 一个整数,表示第i 个组合的组合奖励 B_i(1≦B_i≦10,000) 。2 第二个整数是一个整数,表示有多少个偶像满足该组合的条件。 C_i(3≦C_i≦N) 。继续 3 第一个之后的整数 第 j (1≦j≦C_i) 个整数是表示满足条件的偶像的数量的整数。 I_{i,j}(1≦I_{i,j}≦N) 。这时, 如果j≠k ,I_{i,j} ≠ I_{i,k} 。
出力
单位的最大最终能力值。 1 行输出。 从
在输出末尾插入换行符。 从第
入力例1
10 1 100 200 300 400 500 600 700 800 900 1000 1000 3 1 2 3
出力例1
6100
1 起 至 3 番目、5 起 至 10 直到 9 当你选择一个人的偶像并组建一个单位时,基本能力值为 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