钥匙和宝箱

题目描述

有 $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

购买钥匙 $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 \le N \le 12$
• $1 \le M \le 10^3$
• $1 \leq a_i \leq 10^5$
• $1 \leq b_i \leq N$
• $1 \leq c_{i1} \lt c_{i2} \lt ... \lt c_{i{b_i}} \leq N$