Background

Special for beginners, ^_^

Description

徐老师一家人带着 $N$ 个箱子去旅行了，不幸的事。下了飞机，到了目的地，他发现好像把所有箱子的钥匙搞丢了（也可能是忘记带了）。

幸运的是，他发现可以花钱摆平。当地有 $M$ 个锁匠，第 $i$ 个锁匠能够打开其中的部分箱子，出场费为 $a_i$ ，不论开多少把锁，开锁只收取出场费。

问徐老师至少要破财多少元才能打开所有行李箱。如果不能打开所有行李箱，输出-1。

Format

Input

第一行两个正整数 $N（<13）$ 和 $M（\le1000）$ ，分别表示旅行箱的数量和锁匠的数量。

后面的的 $2M$ 行按照锁匠的编号描述这 $M$ 个锁匠的情况。

对于每个锁匠，第一行有两个正整数 $a（\le10^5）、b$ ，分别表示出场费和能够打开的箱子数量。

第二行给出 $b$ 个正整数，分别表示能够打开的箱子的编号。

Output

如果能打开所有行李箱。输出最小的费用；否则输出-1。

Samples

2 3
1 1
1
2 1
2
3 2
1 2

3

Limitation

1s, 1024KiB for each test case.