← 返回题目列表

AtCoder · abc142_e

E. 得到一切

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有 N 上锁的宝箱,已编号 1 to 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.


示例输入 1

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

示例输出 1

25

我们可以通过购买第一把和第二把钥匙来解锁所有的盒子,代价是 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