题目描述

有 $N$ 个上锁的宝箱，编号为 $1$ 到 $N$。

商店出售 $M$ 把钥匙，第 $i$ 把钥匙锁需要的代价为 $a_i$，能解锁 $b_i$ 个箱子，编号分别是 $c_{i,1},c_{i,2}，c_{i,3}…c_{i,b_i}$ 。 需要注意的是，钥匙一旦购买可以多次使用。

现在想打开所有的箱子，请问最小代价是多少。 如果不可能全部打开，直接输出 -1。

输入

第一行两个整数$N,M$

接下来一共$m$组

每组第一行两个整数$a_i,b_i$

接下来一共$m$个元素表示$C_mb_i$

输出

输出解锁所有宝箱所需的最小开销。

如果无法解锁所有宝箱，则输出 −1。

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

25

样例解释

我们可以通过购买第一和第二把钥匙，花费 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\ <\ =\ N\ <\ =\ 12$
• $1\ <\ =\ M\ <\ =\ 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 $