题目描述

We have $N$ locked treasure boxes, numbered $1$ to $N$.

A shop sells $M$ keys. The $i$-th key is sold for $a_i$ yen (the currency of Japan), and it can unlock $b_i$ of the boxes: Box $c_{i1}$, $c_{i2}$, $...$, $c_{i{b_i}}$. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print $-1$.

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

样例 #1

样例输入 #1

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

样例输出 #1

25

样例 #2

样例输入 #2

12 1
100000 1
2

样例输出 #2

-1

样例 #3

样例输入 #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

说明

数据规模与约定

• 输入值均为整数
• $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} \lt c_{i2} \lt ... \lt c_{i{b_i}} \leq N$

样例 $1$ 解释

我们可以通过购买第一把和第二把钥匙来解锁所有的盒子，成本为 $25$ 日元，这是所需的最低成本。

样例 $2$ 解释

我们无法解锁所有盒子。