题目描述

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

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

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

输入格式

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

$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$ を出力せよ。

题目大意

有 $N$ 个上锁的宝箱，编号为 $1$ 到 $N$。

商店出售 $M$ 把钥匙，第 $i$ 把钥匙锁需要的代价为 $a_i$，能解锁 $b_i$ 个箱子，编号分别是 $c_{i,1},c_{i,2}，c_{i,3}…c_{i,b_i}$ 。 需要注意的是，钥匙一旦购买可以多次使用。

现在想打开所有的箱子，请问最小代价是多少。 如果不可能全部打开，直接输出 -1。

2 3
10 1
1
15 1
2
30 2
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

提示

制約

• 入力は全て整数
• $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 $

Sample Explanation 1

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

Sample Explanation 2

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