Get Everything

题目描述

我们有 $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$。

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 \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$我们可以通过购买第一把和第二把钥匙来打开所有宝箱，费用为 $25$ 日元，这是所需的最小费用。
我们无法打开所有宝箱。

标签: AtCoder|abc142E

来源

AtCoder|abc142E