[ABC142E] Get Everything
题意翻译
有 $N$ 个上锁的宝箱,编号为 $1$ 到 $N$。
商店出售 $M$ 把钥匙,第 $i$ 把钥匙锁需要的代价为 $a_i$,能解锁 $b_i$ 个箱子,编号分别是 $c_{i,1},c_{i,2},c_{i,3}…c_{i,b_i}$
。
需要注意的是,钥匙一旦购买可以多次使用。
现在想打开所有的箱子,请问最小代价是多少。
如果不可能全部打开,直接输出 `-1`。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc142/tasks/abc142_e
鍵のかかった宝箱が $ 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 $ を出力せよ。
输入输出样例
输入样例 #1
2 3
10 1
1
15 1
2
30 2
1 2
输出样例 #1
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
说明
### 制約
- 入力は全て整数
- $ 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
全ての宝箱を開けることは出来ません。