問題文

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

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

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

制約

• 入力は全て整数
• $1 ≤ N ≤ 12$
• $1 ≤ M ≤ 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$ を出力せよ。

入力例 1

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

出力例 1

25

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

入力例 2

12 1
100000 1
2

出力例 2

-1

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

入力例 3

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

出力例 3

69942