题目描述

有 $N$ 把锁和 $M$ 把可制造的钥匙。制造第 $i$ 把钥匙需要 $T_i$ 单位时间，并可以打开指定的 $C_i$ 把锁。每把钥匙最多制造一次。

请选择若干把钥匙打开全部锁，使总制造时间最少。如果无法打开全部锁，输出 $-1$。

输入格式

第一行包含两个整数 $N,M$。

接下来依次描述 $M$ 把钥匙。每把钥匙的第一行包含两个整数 $T_i,C_i$，第二行包含 $C_i$ 个锁的编号。

输出格式

输出打开全部锁所需的最少总时间；若无法完成，输出 $-1$。

样例

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

25

数据范围与提示

• $1\le N\le12$
• $1\le M\le10^3$
• $1\le T_i\le10^5$
• $1\le C_i\le N$
• $1\le X_{i,j}\le N$