分数: 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