配点 : $500$ 点

問題文

鍵のかかった宝箱が $N$ 個あり、$1$ から $N$ までの番号がつけられています。

店で $M$ 個の鍵が売られています。$i$ 個目の鍵は $a_i$ 円で販売されており、$b_i$ 種類の宝箱 $c_{i1}$ , $c_{i2}$ , ..., $c_{i{b_i}}$ を開けることが出来ます。購入した鍵は何度でも使うことが出来ます。

全ての宝箱を開ける為に必要な費用の最小値を答えてください。全ての宝箱を開けることが不可能である場合は $-1$ を出力してください。

制約

• 入力は全て整数
• $1 \leq N \leq 12$
• $1 \leq M \leq 10^3$
• $1 \leq a_i \leq 10^5$
• $1 \leq b_i \leq N$
• $1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$a_1$ $b_1$

$c_{11}$ $c_{12}$ $...$ $c_{1{b_1}}$

$:$

$a_M$ $b_M$

$c_{M1}$ $c_{M2}$ $...$ $c_{M{b_M}}$

出力

全ての宝箱を開ける為に必要な費用の最小値を出力せよ。 全ての宝箱を開けることが不可能である場合は $-1$ を出力せよ。

2 3
10 1
1
15 1
2
30 2
1 2

25

鍵 $1$ と鍵 $2$ を購入すると、全ての宝箱を開けることが出来ます。このときの費用は $25$ 円であり、これが最小値です。

12 1
100000 1
2

-1

全ての宝箱を開けることは出来ません。

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

69942