AT_donuts_2015_2 Tokyo 7th シスターズ

[problemUrl]: https://atcoder.jp/contests/donuts-2015/tasks/donuts_2015_2 [](http://t7s.jp/)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 $ 行に出力せよ。 出力の末尾に改行を入れること。

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