ビット全探索 練習問題 2 D(Beta)編（paizaランク B 相当）

N M
P_1 P_2 ... P_N
k_1 a_{1,1} a_{1,2} ... a_{1,k_1}
k_2 a_{2,1} a_{2,2} ... a_{2,k_1}
...
k_M a_{M,1} a_{M,2} ... a_{M,k_M}

・ 1 行目には、駄菓子の種類数 N とセットの種類数 M が与えられます。
・ 2 行目には、i 番目の駄菓子のセットの値段 P_i が与えられます。
・ 続く M 行の i 行目には、i 番目のセットに含まれる駄菓子の種類数 k_i と含まれる駄菓子 a_{i,j} が与えられます。
・ 入力は合計で N+2 行からなり、入力値最終行の末尾に改行が 1 つ入ります。

すべての種類の駄菓子を手に入れるには、最低でいくら必要か出力してください。
ただし、どのようにセットを購入してもすべての種類の駄菓子を手に入れることができない場合は -1 を出力してください。

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N ≦ 18
・ 1 ≦ M ≦ 18
・ 1 ≦ P_i ≦ 10^9
・ 1 ≦ k_i ≦ N
・ 1 ≦ a_1 < a_2 < ... < a_{k_i} ≦ N

3 3
1 4 2
1 1
3 1 2 3
2 1 3

4

16 13
380755564 71110039 238064682 15271870 464265502 892998763 386986771 178846063 219897128 910815512 420936863 356835190 922848899
6 1 2 9 11 15 16
10 2 3 5 7 8 9 10 12 13 16
9 1 4 5 6 9 10 13 14 16
13 1 2 4 5 7 8 9 10 11 12 13 14 15
13 1 2 3 5 6 7 8 9 10 11 13 14 15
1 14
4 1 4 6 16
14 1 2 3 4 5 6 7 8 9 10 11 12 15 16
3 2 3 14
13 1 2 3 6 7 8 9 10 11 13 14 15 16
11 2 3 4 6 9 10 11 12 14 15 16
12 1 3 4 5 6 7 10 11 12 13 15 16
16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

194117933

17 1
945100933
3 1 7 14

-1