AT_donuts_2015_2 Tokyo 7th シスターズ

[problemUrl]: https://atcoder.jp/contests/donuts-2015/tasks/donuts_2015_2 [](http://t7s.jp/)[《东京 7th Sisters》](https://mzh.moegirl.org.cn/%E4%B8%9C%E4%BA%AC_7th_Sisters)是一款集成了偶像育成、音乐节奏和文字冒险三大要素的手机网络社交游戏，可以在 iPhone 和 Android 设备上玩。 您正在考虑某些游戏规格的简化版本。 在这款简化规格的游戏中，可以从众多偶像中选择九个不同的偶像，组成一个单位进行节奏游戏和舞台对战。在这种情况下，游戏中使用的单位的基本能力值由所选偶像的能力值总和决定。 游戏还有一个连击系统，玩家可以通过满足连击要求获得连击奖励。如果一个单位有三个或三个以上的成员满足组合规定的条件，该单位就会获得该组合的奖励。对于每个组合，你都可以提前知道哪些偶像将满足指定条件。 单位的最终能力值是单位的基础能力值加上所有组合奖励的总和。 我们希望通过组合偶像来尽可能提高单位的最终能力值。 找出最大最终能力值。 请注意，本题中的单位组合和组合是简化规格，与《东京 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} $ - 第$ 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 $ 个组合的信息，用空格分隔。 组合信息由几个整数组成，其中第一个整数 $ B_i（1≤ B_i≤10,000）$代表第 $ i $ 个组合的组合奖金。第二个整数 $ 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 #### 样例输入 #1 ``` 10 1 100 200 300 400 500 600 700 800 900 1000 1000 3 1 2 3 ``` #### 样例输出 #1 ``` 6100 ``` ### 样例 #2 #### 样例输入 #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 ``` ### 样例 #3 #### 样例输入 #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 ```

### Sample Explanation 1 $ 1 $ 番目から $ 3 $ 番目、$ 5 $ 番目から $ 10 $ 番目までの $ 9 $ 人のアイドルを選んでユニットを組むと、基礎能力値が $ 5100 $、コンボボーナスが $ 1000 $ となり、最終的な能力値は $ 6100 $ になります。 ### Sample Explanation 2 基礎能力値は必ず $ 9000 $ となります。 一例として、 $ 1 $, $ 2 $, $ 4 $, $ 5 $, $ 8 $, $ 9 $, $ 10 $, $ 11 $, $ 12 $ 番目のアイドルを選んでユニットを組むことで、全てのコンボボーナスを得ることが出来ます。