E - Get Everything Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

鍵のかかった宝箱が 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

Score : 500 points

Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

  • All values in input are integers.
  • 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

Input

Input is given from Standard Input in the following format:

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}}

Output

Print the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Sample Input 1

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

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 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

Sample Output 3

69942