题目描述

你来到了一处传说中的宝藏所在地，宝藏被 $N$ 个编号为 $1$ 到 $N$ 的锁牢牢封住，只有打开所有锁才能获取宝藏。

你向一位技艺高超的锁神求助，锁神最多可以为你制造 $M$ 把钥匙。

第 $i$ 把钥匙的制造需要 $T_i$ 个单位时间，并且能够打开 $C_i$ 把锁，这些锁的编号为 $X_{i1}, X_{i2}, …, X_{iC_i}$。

你的目标是选择若干把钥匙，以最少的总制造时间打开所有 $N$ 个锁，获取宝藏。

如果无论如何都无法打开所有锁，请输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示锁的数量和锁神可制造的钥匙数量。

接下来 $M$ 组数据，每组描述一把钥匙。

每组数据的第一行包含两个整数 $T_i$ 和 $C_i$，分别表示第 $i$ 把钥匙的制造时间和它能打开的锁数量。

第二行包含 $C_i$ 个整数 $X_{i1}, X_{i2}, …, X_{iC_i}$，表示这把钥匙能打开的锁编号。

输出格式

输出一个整数，表示打开所有锁的最小总制造时间。如果无法打开所有锁，输出 $-1$。

样例 #1

输入

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

输出

25

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 12$，$1 \le M \le 10^3$，$1 \le T_i \le 10^5$，$1 \le X_i \le N$。