/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
Tokyo 7th シスターズは、iPhoneやAndroidでプレイ可能な、アイドル育成カード＆リズムアドベンチャーゲームです。 あなたは、このゲームのいくつかの仕様を簡略化したものについて考えています。
いくつかの仕様が簡略化されたこのゲームでは、 複数人のアイドルの中から異なる 9 人を選び、ユニットを 1 つ組むことで、リズムゲームをしたり、ステージバトルを行うことが可能です。 この際、ゲームで使われるユニットの基礎能力値は、選んだアイドルの能力値の和で決まります。
また、このゲームにはコンボというシステムがあり、コンボの条件を満たすことでコンボボーナスを得られます。 組んだユニットにコンボで指定されている条件を満たすメンバーが 3 人以上いれば、そのコンボのボーナスを得ることが出来ます。 各コンボについて、どのアイドルが指定されている条件を満たすかあらかじめ分かっています。
ユニットの最終的な能力値は、ユニットの基礎能力値に得られた全てのコンボボーナスの和を足したものです。
あなたは、アイドルを組み合わせて、ユニットの最終的な能力値を出来るだけ大きくしたいと思っています。最終的な能力値の最大値を求めてください。
なお、本問題に出てくるユニットの組み方やコンボは簡略化された仕様であり、Tokyo 7th シスターズの仕様とは少し異なることに注意してください。
入力
入力は以下の形式で標準入力から与えられる．
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