题目描述

我们有 $N$ 个锁着的宝箱，编号从 $1$ 到 $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