AtCoder Beginner Contest 142 - Get Everything

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.

-----Constraints-----
 - All values in input are integers.
 - 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} < c_{i2} < ... < c_{i{b_i}} \leq N

-----Input-----
Input is given from Standard Input in the following format:
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}}

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

-----Sample Input-----
2 3
10 1
1
15 1
2
30 2
1 2

-----Sample Output-----
25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Source: atcoder | Difficulty: MEDIUM


Solutions:
(n, m) = map(int, input().split())
dp = [float('inf')] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	key = 0
	for j in c:
		key += 2 ** (j - 1)
	for j in range(len(dp)):
		dp[j | key] = min(dp[j | key], dp[j] + a)
print(dp[-1] if dp[-1] != float('inf') else -1)


(n, m) = map(int, input().split())
ac = []
for _ in range(m):
	(ai, bi) = map(int, input().split())
	ci = list(map(lambda x: 2 ** (int(x) - 1), input().split()))
	ac.append((ai, sum(ci)))
INF = 100 ** 18
dp = [INF] * 2 ** n
dp[0] = 0
for (ai, ci) in ac:
	for j in range(0, 2 ** n):
		dp[j | ci] = min(dp[j | ci], dp[j] + ai)
ans = dp[2 ** n - 1]
if ans == INF:
	print(-1)
	exit()
print(ans)


(N, M) = list(map(int, input().split()))
K = []
for _ in range(M):
	(a, _) = list(map(int, input().split()))
	k = 0
	for i in [int(a) - 1 for a in input().split()]:
		k |= 1 << i
	K.append((a, k))
dp = [10 ** 18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
	for (a, k) in K:
		if dp[state | k] > dp[state] + a:
			dp[state | k] = dp[state] + a
ans = dp[(1 << N) - 1]
print(ans if ans < 10 ** 18 else -1)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, m) = list(map(int, input().split()))
	keys = []
	for _ in range(m):
		bit = ['0'] * n
		(a, b) = list(map(int, input().split()))
		C = list(map(int, input().split()))
		for c in C:
			bit[c - 1] = '1'
		bit = int(''.join(bit), 2)
		keys.append([bit, a])
	dp = [f_inf] * (1 << n)
	dp[0] = 0
	for i in range(1 << n):
		for (k, cost) in keys:
			idx = i | k
			dp[idx] = min(dp[idx], dp[i] + cost)
	print(dp[-1] if dp[-1] != f_inf else -1)

def __starting_point():
	resolve()
__starting_point()


(n, m) = map(int, input().split())
key = []
for _ in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	bi = 0
	for i in c:
		bi += 2 ** (i - 1)
	key.append([a, bi])
dp = [10 ** 10] * 2 ** n
dp[0] = 0
for k in key:
	for b in range(2 ** n):
		dp[b | k[1]] = min(dp[b | k[1]], dp[b] + k[0])
if dp[-1] == 10 ** 10:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
dp = [10 ** 10] * (1 << N)
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = 0
	for j in c:
		d |= 1 << j - 1
	for k in range(1 << N):
		dp[k | d] = min(dp[k | d], dp[k] + a)
if dp[-1] == 10 ** 10:
	print(-1)
else:
	print(dp[-1])


ans = 10 ** 7
(n, m) = map(int, input().split())
dp = [float('inf')] * 2 ** n
dp[0] = 0
prices = []
for i in range(m):
	(a, s) = map(int, input().split())
	prices.append(a)
	f = 0
	for k in map(int, input().split()):
		f += 2 ** (k - 1)
	for j in range(2 ** n - 1, -1, -1):
		dp[j | f] = min(dp[j] + a, dp[j | f])
print(-1 if dp[-1] == float('inf') else dp[-1])


(n, m) = map(int, input().split())
(a, c) = ([], [])
for _ in range(m):
	a.append(list(map(int, input().split()))[0])
	c.append(sum((1 << int(i) - 1 for i in input().split())))
inf = float('inf')
dp = [inf] * (1 << n)
dp[0] = 0
for i in range(2 ** n):
	for j in range(m):
		dp[i | c[j]] = min(dp[i | c[j]], dp[i] + a[j])
print(dp[-1] if inf != dp[-1] else -1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
inf = float('inf')
p = 2 ** n
dp = [inf] * p
dp[0] = 0
for _ in range(m):
	(a, _) = map(int, input().split())
	c = sum([2 ** (i - 1) for i in map(int, input().split())])
	for i in range(p):
		if dp[i | c] > dp[i] + a:
			dp[i | c] = dp[i] + a
if dp[-1] == inf:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
Inf = 10 ** 8
Dp = [Inf] * 2 ** N
Dp[0] = 0
for i in range(M):
	(a, _) = map(int, input().split())
	c = list(map(int, input().split()))
	d = sum((1 << p - 1 for p in c))
	for j in range(2 ** N):
		ope = j | d
		Dp[ope] = min(Dp[ope], Dp[j] + a)
if Dp[-1] == Inf:
	print(-1)
else:
	print(Dp[-1])


INF = float('inf')
(N, M) = map(int, input().split())
dp = [INF] * 2 ** N
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	C = [int(i) for i in input().split()]
	mask = sum((1 << c - 1 for c in C))
	for (i, dpi) in enumerate(dp):
		if dp[i | mask] > dpi + a:
			dp[i | mask] = dpi + a
ans = dp[-1]
print(-1 if ans == INF else ans)


(n, m) = map(int, input().split())
dp = [10 ** 9] * 2 ** n
dp[0] = 0
for _ in range(m):
	(a, _) = map(int, input().split())
	c = list(map(int, input().split()))
	t = 0
	for x in c:
		t |= 1 << x - 1
	for b in range(2 ** n):
		if dp[b | t] > dp[b] + a:
			dp[b | t] = dp[b] + a
if dp[-1] > 10 ** 8:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
l = []
for _ in range(M):
	(a, b) = map(int, input().split())
	(*c,) = map(int, input().split())
	l.append((a, c))
inf = 10 ** 12
dp = [inf] * 2 ** N
dp[0] = 0
for i in range(2 ** N):
	for (cost, j) in l:
		v = sum(map(lambda x: 2 ** (x - 1), j))
		dp[i | v] = min(dp[i | v], dp[i] + cost)
print(dp[2 ** N - 1] if dp[2 ** N - 1] != inf else -1)


import sys
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	U = 2 ** n
	dp = [[float('inf')] * 2 ** n for _ in range(m)]
	dp[0][0] = 0
	for i in range(1, m):
		(a, b) = map(int, input().split())
		k = map(int, input().split())
		c = 0
		for l in k:
			c |= 1 << l - 1
		for j in range(U):
			dp[i][j] = min(dp[i - 1][j & ~c] + a, dp[i - 1][j])
	if dp[m - 1][2 ** n - 1] == float('inf'):
		print(-1)
	else:
		print(dp[m - 1][2 ** n - 1])

def __starting_point():
	main()
__starting_point()


(n, m) = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	ngo = 0
	for j in input().split(' '):
		ngo += 2 ** (int(j) - 1)
	for j in range(2 ** n):
		if dp[j | ngo] > dp[j] + a:
			dp[j | ngo] = dp[j] + a
if dp[2 ** n - 1] == float('inf'):
	print(-1)
	exit(0)
print(dp[2 ** n - 1])


import math
(N, M) = map(int, input().split())
dp = [math.inf] * pow(2, N)
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum([pow(2, int(i) - 1) for i in input().split()])
	for i in range(pow(2, N)):
		dp[i | c] = min(dp[i | c], dp[i] + a)
print(dp[-1] if dp[-1] != math.inf else -1)


(n, m) = list(map(int, input().split()))
can_open = []
cost = []
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	cost.append(a)
	can_open.append(sum((1 << c - 1 for c in map(int, input().split()))))
n_bit = 1 << n
INF = 10 ** 18
dp = [INF] * n_bit
dp[0] = 0
for (x, y) in zip(can_open, cost):
	for j in range(n_bit):
		m = j | x
		z = dp[j] + y
		if dp[m] > z:
			dp[m] = z
print(dp[-1] if dp[-1] != INF else -1)


(n, m) = map(int, input().split())
INF = 10 ** 9
dp = [INF for i in range(2 ** n)]
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	tmp = 0
	for j in list(map(int, input().split())):
		tmp += 2 ** (j - 1)
	dp[tmp] = min(dp[tmp], a)
for i in range(2 ** n):
	for j in range(2 ** n):
		dp[i | j] = min(dp[i] + dp[j], dp[i | j])
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
a_list = []
c = []
for i in range(m):
	(a, b) = map(int, input().split())
	a_list.append(a)
	c.append(sum((1 << j - 1 for j in list(map(int, input().split())))))
inf = 10 ** 10
dp = [inf] * (1 << n)
dp[0] = 0
for i in range(1 << n):
	for j in range(m):
		dp[c[j] | i] = min(dp[c[j] | i], dp[i] + a_list[j])
if dp[-1] == inf:
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
l = []
for i in range(m):
	(a, b) = map(int, input().split())
	c = [int(x) for x in input().split()]
	s = 0
	for j in c:
		s += 2 ** (j - 1)
	l.append([s, a])
v = [10 ** 7 for x in range(2 ** n)]
v[0] = 0
for (s, a) in l:
	for j in range(2 ** n):
		if v[j] != 10 ** 7:
			v[j | s] = min(v[j | s], v[j] + a)
print(v[2 ** n - 1] if v[2 ** n - 1] != 10 ** 7 else -1)


def main():
	(N, M) = map(int, input().split())
	L = 2 ** N
	inf = 10 ** 8
	dp = [inf for i in range(L)]
	dp[0] = 0
	for i in range(M):
		(a, _) = map(int, input().split())
		key = sum([2 ** (int(i) - 1) for i in input().split()])
		for j in range(L):
			q = j | key
			dp[q] = min(dp[j] + a, dp[q])
	ans = dp[L - 1]
	print(ans if ans < inf else -1)
main()


def resolve():
	(N, M) = map(int, input().split())
	DP = [10 ** 8 + 1 for _ in range(1 << N)]
	DP[0] = 0
	for _ in range(M):
		(a, _) = map(int, input().split())
		c = list(map(int, input().split()))
		bit = 0
		for j in c:
			bit |= 1 << j - 1
		for j in range(1 << N):
			DP[j | bit] = min(DP[j] + a, DP[j | bit])
	print(DP[-1] if DP[-1] != 10 ** 8 + 1 else -1)
resolve()


(N, M) = map(int, input().split())
key = []
for i in range(M):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	c = 0
	for d in C:
		c += 2 ** (d - 1)
	key.append((a, b, c))
dp = [10 ** 8 + 10] * 2 ** N
dp[0] = 0
for bi in range(0, 2 ** N):
	for i in range(M):
		t = key[i]
		(a, b, c) = t
		dp[bi | c] = min(dp[bi] + a, dp[bi | c])
if dp[-1] < 10 ** 8 + 10:
	print(int(dp[-1]))
else:
	print(-1)


(N, M) = map(int, input().split())
COST = []
B = []
C = []
C_bit = []
INF = 10 ** 18
dp = [INF] * (1 << N)
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	C.append(list(map(int, input().split())))
	COST.append(a)
	B.append(b)
for i in range(M):
	bit = ['0'] * N
	for j in range(B[i]):
		bit[C[i][j] - 1] = '1'
	bit_int = int(''.join(bit), 2)
	C_bit.append(bit_int)
for (cost, c) in zip(COST, C_bit):
	for i in range(1 << N):
		j = i | c
		d = dp[i] + cost
		if dp[j] > d:
			dp[j] = d
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
V = []
INF = float('inf')
dp = [INF] * (1 << N)
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	k = 0
	for j in range(b):
		k |= 1 << c[j] - 1
	V.append((a, k))
	dp[k] = min(dp[k], a)
for i in range(1 << N):
	for (a, k) in V:
		dp[i | k] = min(dp[i | k], dp[i] + dp[k])
print(dp[-1] if dp[-1] != INF else -1)


(N, M) = map(int, input().split())
inf = 1000000000.0 + 7
dp = [inf] * (1 << N)
dp[0] = 0
for m in range(M):
	(a, b) = map(int, input().split())
	hako = list(map(int, input().split()))
	mask = sum((1 << c - 1 for c in hako))
	for i in range(1 << N):
		if dp[i] + a < dp[i | mask]:
			dp[i | mask] = dp[i] + a
if dp[-1] == inf:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
key = []
for _ in range(M):
	(a, b) = map(int, input().split())
	s = 0
	C = list(map(lambda x: int(x) - 1, input().split()))
	for c in C:
		s |= 1 << c
	key += [(s, a)]
dp = [float('inf')] * (1 << N)
dp[0] = 0
for s in range(1 << N):
	for i in range(M):
		t = s | key[i][0]
		cost = dp[s] + key[i][1]
		dp[t] = min(dp[t], cost)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
keys = [None] * M
for i in range(M):
	(cost, b) = map(int, readline().split())
	bit = 0
	target = list(map(int, readline().split()))
	for t in target:
		bit += 1 << t - 1
	keys[i] = (cost, bit)
INF = 10 ** 8 + 1
dp = [INF for i in range(2 ** N)]
dp[0] = 0
for key in keys:
	(cost, bit) = key
	for j in range(len(dp) - 1, -1, -1):
		if dp[j] == -1:
			continue
		if dp[j | bit] > dp[j] + cost:
			dp[j | bit] = dp[j] + cost
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
inf = 12 * 10 ** 5 + 1
dp = [inf for j in range(2 ** N)]
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = sum([1 << i - 1 for i in list(map(int, input().split()))])
	for j in range(2 ** N):
		dp[j | c] = min(dp[j | c], dp[j] + a)
print(dp[2 ** N - 1] if dp[2 ** N - 1] != inf else -1)


import sys
input = sys.stdin.readline

def solve():
	INF = 10 ** 10
	(N, M) = list(map(int, input().split()))
	keys = []
	costs = []
	for _ in range(M):
		(a, b) = list(map(int, input().split()))
		costs.append(a)
		cs = list(map(int, input().split()))
		key = 0
		for c in cs:
			key |= 1 << c - 1
		keys.append(key)
	dp = [INF] * (1 << N)
	dp[0] = 0
	for (key, cost) in zip(keys, costs):
		for S in reversed(list(range(1 << N))):
			S2 = S | key
			c2 = dp[S] + cost
			if c2 < dp[S2]:
				dp[S2] = c2
	if dp[-1] == INF:
		print(-1)
	else:
		print(dp[-1])
solve()


(n, m) = map(int, input().split())
dp = [float('inf')] * 2 ** n
dp[0] = 0
for _ in range(m):
	(a, _) = map(int, input().split())
	c = sum([2 ** (int(i) - 1) for i in input().split()])
	for s in range(2 ** n):
		t = s | c
		if dp[t] > dp[s] + a:
			dp[t] = dp[s] + a
ans = dp[-1]
if ans == float('inf'):
	ans = -1
print(ans)


(N, M) = map(int, input().split())
dp = [float('INF')] * 2 ** N
dp[0] = 0
for i in range(1, M + 1):
	(a, b) = map(int, input().split())
	tmp = 0
	for c in list(map(int, input().split())):
		tmp += 1 << c - 1
	for j in range(2 ** N):
		target = j | tmp
		dp[target] = min(dp[j] + a, dp[target])
if dp[-1] == float('INF'):
	print(-1)
else:
	print(dp[-1])


import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : list(map(int, sys.stdin.readline().split()))
na = lambda : list(map(int, sys.stdin.readline().split()))

def main():
	(n, m) = ns()
	d = []
	for _ in range(m):
		(ai, bi) = ns()
		ci = na()
		d.append([ai, bi, ci])
	dp = [INF for _ in range(2 ** n)]
	dp[0] = 0
	for (ai, bi, ci) in d:
		getkey = 0
		for cii in ci:
			cii -= 1
			getkey += 1 << cii
		for i in range(2 ** n):
			dp[i | getkey] = min(dp[i | getkey], dp[i] + ai)
	tmp = dp[2 ** n - 1]
	print(tmp if tmp != INF else -1)

def __starting_point():
	main()
__starting_point()


from sys import stdin
(n, m) = map(int, stdin.readline().rstrip().split())
c = []
a_list = []

def main():
	for i in range(m):
		(a, b) = map(int, stdin.readline().rstrip().split())
		a_list.append(a)
		c.append(sum((1 << j - 1 for j in list(map(int, stdin.readline().rstrip().split())))))
	inf = 10 ** 10
	dp = [inf] * (1 << n)
	dp[0] = 0
	for i in range(1 << n):
		for (A, C) in zip(a_list, c):
			dp[C | i] = min(dp[C | i], dp[i] + A)
	if dp[-1] == inf:
		print(-1)
	else:
		print(dp[-1])

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
kagi = []
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	kagi.append([a, b, c])
for j in range(m):
	for i in range(1 << n):
		tmp = i + 0
		for k in kagi[j][2]:
			tmp = tmp | 1 << k - 1
		dp[tmp] = min(dp[tmp], dp[i] + kagi[j][0])
print(dp[(1 << n) - 1] if dp[(1 << n) - 1] != float('inf') else -1)


(n, m) = map(int, input().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	bit = 0
	for e in map(int, input().split()):
		bit += 1 << e - 1
	for i in range(1 << n):
		dp[i | bit] = min(dp[i | bit], dp[i] + a)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
trs = []
for _ in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	cnt = 0
	for i in range(b):
		cnt += 2 ** (c[i] - 1)
	trs.append((a, cnt))
dp = [10 ** 9] * 2 ** n
dp[0] = 0
for i in range(2 ** n):
	for (a, cnt) in trs:
		dp[i | cnt] = min(dp[i] + a, dp[i | cnt])
if dp[2 ** n - 1] != 10 ** 9:
	print(dp[2 ** n - 1])
else:
	print(-1)


(n, m) = map(int, input().split())
inf = 1000000000.0
dp = [inf] * (1 << n)
dp[0] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	cs = list(map(int, input().split()))
	r = 0
	for c in cs:
		r |= 1 << c - 1
	for i in range(1 << n):
		if dp[i | r] > dp[i] + a:
			dp[i | r] = dp[i] + a
if dp[(1 << n) - 1] == inf:
	print('-1')
else:
	print('{}'.format(dp[(1 << n) - 1]))


(n, m) = map(int, input().split())
valists = [10 ** 9 for _ in range(1 << n)]
valists[0] = 0
for i in range(m):
	(values, b) = map(int, input().split())
	c = list(map(int, input().split()))
	cnt = 0
	for j in range(b):
		cnt += 2 ** (c[j] - 1)
	for j in range(len(valists)):
		x = j | cnt
		valists[x] = min(valists[x], valists[j] + values)
ans = valists[2 ** n - 1]
if ans != 10 ** 9:
	print(ans)
else:
	print(-1)


(N, M) = map(int, input().split())
key = []
for i in range(M):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	s = 0
	for i in range(b):
		C[i] -= 1
		s = s | 1 << C[i]
	key.append((s, a))
INF = float('inf')
dp = [INF for _ in range(1 << N)]
dp[0] = 0
for s in range(1 << N):
	for i in range(M):
		t = s | key[i][0]
		dp[t] = min(dp[t], dp[s] + key[i][1])
if dp[-1] == INF:
	ans = -1
else:
	ans = dp[-1]
print(ans)


(N, M) = map(int, input().split())
INF = 10 ** 10
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	key = 0
	for j in range(len(c)):
		key += 1 << c[j] - 1
	for j in range(len(dp) - 1, -1, -1):
		if dp[j] == INF:
			continue
		dp[j | key] = min(dp[j | key], dp[j] + a)
print((dp[-1], -1)[dp[-1] == INF])


def main():
	inf = 10 ** 8 + 1
	(N, M) = list(map(int, input().split()))
	dp = [inf] * (1 << N)
	dp[0] = 0
	for _ in range(M):
		(price, _) = list(map(int, input().split()))
		c = (int(x) - 1 for x in input().split())
		k = sum((1 << x for x in c))
		for bit in reversed(list(range(1 << N))):
			nbit = bit | k
			dp[nbit] = min(dp[nbit], dp[bit] + price)
	ans = dp[(1 << N) - 1]
	if ans == inf:
		print(-1)
	else:
		print(ans)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
asl = []
for _ in range(M):
	(a, b) = map(int, input().split())
	cl = list(map(int, input().split()))
	s = 0
	for c in cl:
		s += 1 << c - 1
	asl.append([a, s])
INF = 10 ** 8
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(2 ** N):
	for as_v in asl:
		(a, s) = as_v
		dp[i | s] = min(dp[i] + a, dp[i | s])
ans = dp[2 ** N - 1]
if ans == INF:
	print(-1)
else:
	print(ans)


(n, m) = map(int, input().split())
l = []
for _ in range(m):
	(a, b) = map(int, input().split())
	cl = [x - 1 for x in map(int, input().split())]
	b = 0
	for i in cl:
		b |= 1 << i
	l.append([a, b])
inf = 10 ** 9
dp = [inf] * 2 ** n
dp[0] = 0
for x in range(2 ** n):
	for i in range(m):
		(a, b) = l[i]
		dp[x | b] = min(dp[x | b], dp[x] + a)
if dp[-1] == inf:
	print(-1)
else:
	print(dp[-1])


def main():
	I = lambda : list(map(int, input().split()))
	(n, m) = I()
	e = [(I()[0], [1 << n - i for i in I()]) for _ in '_' * m]
	I = 9 ** 9
	dp = [I] * 2 ** n
	dp[0] = 0
	for (i, d) in enumerate(dp):
		if d == I:
			continue
		for (a, c) in e:
			(b, x) = (i, d + a)
			for j in c:
				b |= j
			if dp[b] > x:
				dp[b] = x
	print(-(dp[-1] == I) or dp[-1])
main()


(N, M) = map(int, input().split())
dp = [float('INF')] * 2 ** N
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	key = 0
	for c in C:
		key += 1 << c - 1
	for j in range(2 ** N - 1, -1, -1):
		dp[j | key] = min(dp[j | key], dp[j] + a)
if dp[-1] == float('INF'):
	print(-1)
else:
	print(dp[-1])


import sys
input = sys.stdin.readline
INF = float('inf')

def main():
	(N, M) = list(map(int, input().split()))
	keys = [None] * M
	for i in range(M):
		(a, b) = list(map(int, input().split()))
		s = 0
		for c in map(int, input().split()):
			c -= 1
			s |= 1 << c
		keys[i] = (s, a)
	dp = [INF] * 2 ** N
	dp[0] = 0
	for s in range(2 ** N):
		for (key, a) in keys:
			t = s | key
			dp[t] = min(dp[t], dp[s] + a)
	ans = dp[-1] if dp[-1] != INF else -1
	print(ans)

def __starting_point():
	main()
__starting_point()


I = lambda : map(int, input().split())
(n, m) = I()
d = [0] + [9 ** 9] * 2 ** n
while m:
	m -= 1
	(a, _) = I()
	s = sum((1 << c - 1 for c in I()))
	for j in range(2 ** n):
		d[s | j] = min(d[s | j], d[j] + a)
print(d[-2] % 9 ** 9 or -1)


(n, m) = map(int, input().split())
A = []
for i in range(m):
	(a, b) = map(int, input().split())
	C = [int(i) for i in input().split()]
	x = 0
	for c in C:
		x |= 1 << c - 1
	A.append((a, x))
DP = [float('inf')] * 2 ** n
DP[0] = 0
for i in range(m):
	(a, x) = A[i]
	for j in range(2 ** n):
		DP[j | x] = min(DP[j | x], DP[j] + a)
print(-1 if DP[2 ** n - 1] == float('inf') else DP[2 ** n - 1])


(N, M) = map(int, input().split())
dp = [0] + [1 << 100] * ((1 << N) - 1)
for _ in range(M):
	dppre = dp
	(a, b) = map(int, input().split())
	C = [int(a) - 1 for a in input().split()]
	mask = sum([1 << C[i] for i in range(b)])
	for maskpre in range(1 << N):
		new = mask | maskpre
		dp[new] = min(dp[new], dppre[maskpre] + a)
		maskpre -= 1
print(dp[-1] if dp[-1] < 1 << 100 else -1)


(n, m) = map(int, input().split())
keys = [None] * m
INF = 10 ** 10
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	cond = 0
	for j in c:
		cond += 2 ** (j - 1)
	keys[i] = [a, cond]
for key in keys:
	for sta in range(2 ** n):
		dp[sta | key[1]] = min(dp[sta | key[1]], dp[sta] + key[0])
print(dp[-1] if dp[-1] != INF else -1)


(N, M) = map(int, input().split())
INF = 10 ** 7
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	d = sum((1 << i - 1 for i in map(int, input().split())))
	for j in range(2 ** N):
		if dp[j] == INF:
			continue
		jord = j | d
		dp[jord] = min(dp[j] + a, dp[jord])
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


def main():
	(n, m) = list(map(int, input().split()))
	DP = [10 ** 9] * 2 ** n
	DP[0] = 0
	updated_patterns = {0}
	for _ in range(m):
		(cost, types) = list(map(int, input().split()))
		to_open = list(map(int, input().split()))
		openable = 0
		for open in to_open:
			openable += 1 << open - 1
		new_updated = set()
		for opened in updated_patterns:
			pattern = opened | openable
			new_cost = DP[opened] + cost
			if DP[pattern] > new_cost:
				DP[pattern] = new_cost
				new_updated.add(pattern)
		updated_patterns |= new_updated
	full_open = 2 ** n - 1
	ans = DP[full_open]
	if ans == 10 ** 9:
		ans = -1
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
INF = 10 ** 18
dp = [INF] * (1 << N)
dp[0] = 0
cost = [None] * M
target = [0] * M
for i in range(M):
	(cost[i], b) = map(int, input().split())
	c = [int(x) for x in input().split()]
	for j in c:
		target[i] = target[i] | 1 << j - 1
for s in range(1 << N):
	for i in range(M):
		ns = s | target[i]
		dp[ns] = min(dp[ns], dp[s] + cost[i])
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


import sys
from collections import defaultdict

def input():
	return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
sys.setrecursionlimit(20000000)
INF = float('inf')

def main():
	(N, M) = list(map(int, input().split()))
	key = []
	for _ in range(M):
		(a, b) = list(map(int, input().split()))
		C = list([int(x) - 1 for x in input().split()])
		state = 0
		for c in C:
			state += 2 ** c
		key.append((a, state))
	dp = [INF for _ in range(2 ** N)]
	dp[0] = 0
	for i in range(2 ** N - 1):
		for k in range(M):
			state = key[k][1]
			tmp = dp[i] + key[k][0]
			if dp[i | state] > tmp:
				dp[i | state] = tmp
	if dp[-1] == INF:
		print(-1)
	else:
		print(dp[-1])

def __starting_point():
	main()
__starting_point()


def main():
	(N, M) = map(int, input().split())
	inf = 10 ** 15
	p = 1 << N
	dp = [inf] * p
	dp[0] = 0
	for i in range(M):
		(a, b) = map(int, input().split())
		c = sum((1 << i - 1 for i in map(int, input().split())))
		for j in range(p):
			dp[c | j] = min(dp[j] + a, dp[c | j])
	if dp[-1] == inf:
		print(-1)
	else:
		print(int(dp[-1]))
main()


def main():
	(n, m) = map(int, input().split())
	dp = [0] * 2 ** n
	len_dp = len(dp)
	key_list = dict()
	sub = 1
	for i in range(n):
		key_list[i + 1] = sub
		sub *= 2
	for _ in range(m):
		(a, b) = map(int, input().split())
		c = [int(x) for x in input().split()]
		key = 0
		for value in c:
			key += key_list[value]
		for i in range(len_dp - 1, -1, -1):
			if i == 0 or dp[i]:
				if dp[i | key]:
					dp[i | key] = min([dp[i] + a, dp[i | key]])
				else:
					dp[i | key] = dp[i] + a
	print(dp[len_dp - 1] if dp[len_dp - 1] else -1)

def __starting_point():
	main()
__starting_point()


def main():
	(n, m) = map(int, input().split())
	costs = [None] * m
	keys = [None] * m
	pattern = 2 ** n
	inf = 10 ** 12
	dp = [inf] * pattern
	for i in range(m):
		costs[i] = int(input().split()[0])
		keys[i] = sum([1 << int(i) - 1 for i in input().split()])
	dp[0] = 0
	for i in range(pattern):
		for (cost, key) in zip(costs, keys):
			pi = i | key
			if dp[pi] > cost + dp[i]:
				dp[pi] = cost + dp[i]
	if dp[pattern - 1] == inf:
		print(-1)
	else:
		print(dp[pattern - 1])

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
dp = [pow(10, 10) for _ in range(pow(2, n))]
dp[0] = 0
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	cs = list(map(int, input().split()))
	d = 0
	for c in cs:
		d += pow(2, c - 1)
	for i in range(pow(2, n)):
		dp[i | d] = min(dp[i | d], dp[i] + a)
if dp[pow(2, n) - 1] == pow(10, 10):
	print(-1)
else:
	print(dp[pow(2, n) - 1])


(n, m) = map(int, input().split())
keys = []
for i in range(m):
	(a, b) = map(int, input().split())
	s = 0
	for c in map(int, input().split()):
		c -= 1
		s |= 1 << c
	keys.append((s, a))
INF = 1001001001
dp = [INF] * (1 << n)
dp[0] = 0
for s in range(1 << n):
	for (k, v) in keys:
		t = s | k
		cost = dp[s] + v
		dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == INF:
	ans = -1
print(ans)


(n, m) = map(int, input().split())
inf = 10 ** 8 + 1
dp = [inf] * 2 ** n
dp[-1] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	c = sum((2 ** (i - 1) for i in map(int, input().split())))
	for j in range(len(dp)):
		dp[j] = min(dp[j], a + dp[j | c])
if dp[0] == inf:
	print(-1)
else:
	print(dp[0])


(n, m) = map(int, input().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	SS = sum([1 << cc - 1 for cc in c])
	for S in range(1 << n):
		dp[S | SS] = min(dp[S | SS], dp[S] + a)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


import sys

def solve(N, M):
	dp = [float('inf')] * 2 ** N
	dp[0] = 0
	for y in range(1, M + 1):
		(a, b) = list(map(int, input().split()))
		c = [int(i) for i in input().split()]
		t = 0
		for cc in c:
			t |= 1 << cc - 1
		for x in range(2 ** N):
			if dp[x | t] > dp[x] + a:
				dp[x | t] = dp[x] + a
	return -1 if dp[-1] == float('inf') else dp[-1]

def main(args):
	(N, M) = list(map(int, input().split()))
	ans = solve(N, M)
	print(ans)

def __starting_point():
	main(sys.argv[1:])
__starting_point()


(n, m) = list(map(int, input().split()))
g = 1 << n
dp = [float('inf')] * g
dp[0] = 0
for i in range(m):
	(a, b) = list(map(int, input().split()))
	c_l = list(map(int, input().split()))
	f = 0
	for c_i in c_l:
		f += 1 << c_i - 1
	for j in range(g - 1, -1, -1):
		dp[j | f] = min(dp[j] + a, dp[j | f])
print(-1 if dp[-1] == float('inf') else dp[-1])


(n, m) = map(int, input().split())
INF = 10 ** 10
B = [INF] * (1 << n)
B[0] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	opens = 0
	for c in C:
		opens |= 1 << c - 1
	for i in range(2 ** n):
		if B[i | opens] > B[i] + a:
			B[i | opens] = B[i] + a
if B[(1 << n) - 1] == INF:
	print(-1)
else:
	print(B[(1 << n) - 1])


(N, M) = map(int, input().split())
C = []
dp = [10 ** 9 for i in range(1 << N)]
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(lambda x: int(x) - 1, input().split()))
	b = 0
	for i in c:
		b |= 1 << i
	C.append((b, a))
for s in range(1 << N):
	for c in range(M):
		t = s | C[c][0]
		dp[t] = min(dp[t], dp[s] + C[c][1])
print(dp[-1] if dp[-1] != 10 ** 9 else -1)


(n, m) = map(int, input().split())
INF = 10 ** 9
cur = [INF] * 2 ** n
cur[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = 0
	for j in map(int, input().split()):
		c += 2 ** (j - 1)
	(pre, cur) = (cur, [INF] * 2 ** n)
	for j in range(2 ** n):
		cur[j] = min(pre[j], cur[j])
		jc = j | c
		cur[jc] = min(pre[j] + a, cur[jc])
if cur[-1] == INF:
	print(-1)
else:
	print(cur[-1])


(n, m) = map(int, input().split())
t = []
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = 0
	for i in c:
		d += 2 ** (i - 1)
	t.append([a, d])
e = [float('INF')] * 2 ** n
e[0] = 0
for (i, j) in t:
	for h in range(2 ** n):
		e[h | j] = min(i + e[h], e[h | j])
print(e[-1] if e[-1] != float('INF') else -1)


(N, M) = map(int, input().split())
dp = [10 ** 10 for B in range(1 << N)]
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = [int(j) for j in input().split()]
	C = sum([1 << x - 1 for x in c])
	for B in range(1 << N):
		dp[B | C] = min(dp[B | C], dp[B] + a)
if dp[(1 << N) - 1] == 10 ** 10:
	print(-1)
else:
	print(dp[(1 << N) - 1])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
INF = 1 << 30
dp = [INF] * (1 << N)
dp[0] = 0
K = []
for _ in [0] * M:
	(a, b) = map(int, input().split())
	(*C,) = map(int, input().split())
	h = 0
	for c in C:
		h ^= 1 << c - 1
	for i in range(1 << N):
		nxt = i | h
		dp[nxt] = min(dp[nxt], dp[i] + a)
ans = dp[(1 << N) - 1]
print(-1 if ans == INF else ans)


(N, M) = map(int, input().split())
A = [None] * M
K = [None] * M
INF = 10 ** 7
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	k = sum([2 ** (i - 1) for i in map(int, input().split())])
	for j in range(2 ** N):
		dp[j | k] = min(dp[j | k], dp[j] + a)
ans = dp[2 ** N - 1] if dp[2 ** N - 1] < INF else -1
print(ans)


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
INF = 10 ** 18
eps = 10 ** (-7)
(N, M) = list(map(int, readline().split()))
k = 2 ** N
dp = [INF for i in range(k)]
dp[0] = 0
for i in range(M):
	(a, b) = list(map(int, readline().split()))
	c = list(map(int, readline().split()))
	d = sum((1 << ci - 1 for ci in c))
	dpnew = dp[:]
	for j in range(k):
		dpnew[j | d] = min(dp[j] + a, dpnew[j | d])
	dp = dpnew
print(dp[2 ** N - 1] if dp[2 ** N - 1] != INF else -1)


(N, M) = map(int, input().split())
A = [0] * M
keys = [0] * M
for i in range(M):
	(a, b) = map(int, input().split())
	A[i] = a
	c = list(map(int, input().split()))
	for j in range(len(c)):
		keys[i] |= 1 << c[j] - 1
INF = 10 ** 9 + 1
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(len(keys)):
	for j in range(len(dp) - 1, -1, -1):
		if dp[j] != INF:
			dp[j | keys[i]] = min(dp[j | keys[i]], dp[j] + A[i])
print((-1, dp[-1])[dp[-1] != INF])


import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def input():
	return sys.stdin.readline().strip()

def main():
	(N, M) = list(map(int, input().split()))
	dp = [INF for i in range(1 << N)]
	dp[0] = 0
	key = []
	for _ in range(M):
		(a, b) = list(map(int, input().split()))
		C = tuple([int(x) - 1 for x in input().split()])
		status = 0
		for c in C:
			status += 2 ** c
		key.append((a, status))
	for (a, status) in key:
		if dp[status] > a:
			dp[status] = a
	for i in range(2 ** N - 1):
		for (a, status) in key:
			new_status = status | i
			if dp[new_status] > dp[i] + a:
				dp[new_status] = dp[i] + a
	if dp[-1] == INF:
		print(-1)
	else:
		print(dp[-1])

def __starting_point():
	main()
__starting_point()


def min(a, b):
	return a if a <= b else b

def main():
	(n, m) = map(int, input().split())
	inf = 10 ** 9
	cost = [0] * m
	dp = [inf] * (1 << n)
	dp[0] = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		t = sum([1 << int(x) - 1 for x in input().split()])
		for s in range(1 << n):
			dp[t | s] = min(dp[t | s], dp[s] + a)
	print(-1 if dp[-1] == inf else dp[-1])
main()


def main():
	(n, m) = tuple([int(t) for t in input().split()])
	keys = []
	dp = [10 ** 9] * (1 << n)
	dp[0] = 0
	for _ in range(m):
		(a, _) = tuple([int(t) for t in input().split()])
		c = tuple([int(t) for t in input().split()])
		key = 0
		for c_i in c:
			key |= 1 << c_i - 1
		keys.append((a, key))
	for (a, key) in keys:
		for i in range(1 << n):
			dp[i | key] = min(dp[i | key], dp[i] + a)
	if dp[-1] == 10 ** 9:
		print(-1)
	else:
		print(dp[-1])

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
INF = float('inf')
dp = [INF for j in range(2 ** n)]
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = map(int, input().split())
	k = 0
	for ci in c:
		ci -= 1
		k |= 1 << ci
	for j in range(2 ** n):
		l = k | j
		dp[l] = min(dp[l], dp[j] + a)
if dp[2 ** n - 1] == INF:
	print(-1)
else:
	print(dp[2 ** n - 1])


def main():
	(N, M) = map(int, input().split())
	A = [0] * M
	import heapq
	import collections
	from itertools import permutations
	table = collections.defaultdict(list)
	AC = [[0, 0] for i in range(M)]
	C = [set() for i in range(M)]
	for i in range(M):
		(a, b) = map(int, input().split())
		AC[i][0] = a
		tmp = set(map(int, input().split()))
		for x in tmp:
			AC[i][1] |= 1 << x - 1
	dp = [10 ** 9] * 2 ** N
	dp[0] = 0
	for i in range(1, 2 ** N):
		k = 0
		s = set()
		for j in range(1, i):
			if i & j == j:
				dp[i] = min(dp[i], dp[j] + dp[i ^ j])
		for (a, c) in AC:
			if c & i == i:
				dp[i] = min(dp[i], a)
	if dp[-1] == 10 ** 9:
		print(-1)
	else:
		print(dp[-1])
main()


(N, M) = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << N)
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum(map(lambda x: 1 << int(x) - 1, input().split()))
	for j in range(1 << N):
		dp[j | c] = min(dp[j | c], dp[j] + a)
ans = dp[-1]
if ans == INF:
	print(-1)
else:
	print(ans)


(n, m) = map(int, input().split())
digit = ''.join(['0', str(n), 'b'])
cost = [0] + [m * 10 ** 5 + 1] * (2 ** n - 1)
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	cc = 0
	for j in c:
		cc += 2 ** (j - 1)
	for j in range(2 ** n):
		jj = j | cc
		cost[jj] = min(cost[jj], cost[j] + a)
if cost[-1] == m * 10 ** 5 + 1:
	print(-1)
else:
	print(cost[-1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = 0
	for j in list(map(int, input().split())):
		c += 1 << j - 1
	for k in range(1 << n):
		dp[k | c] = min(dp[k | c], dp[k] + a)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
k = []
for i in range(m):
	(a, b) = map(int, input().split())
	c = sum(map(lambda x: 2 ** (int(x) - 1), input().split()))
	k.append((a, c))
dp = [2 ** 100 for i in range(2 ** n)]
dp[0] = 0
for i in k:
	for j in range(2 ** n):
		dp[i[1] | j] = min(dp[i[1] | j], dp[j] + i[0])
if dp[-1] == 2 ** 100:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
inf = 10 ** 10
dp = [inf] * (1 << N)
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum([2 ** (i - 1) for i in map(int, input().split())])
	for j in range(1 << N):
		dp[j | c] = min(dp[j] + a, dp[j | c])
res = dp[-1] if dp[-1] != inf else -1
print(res)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
INF = float('inf')
dp = [INF] * (1 << N)
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	bit = 0
	for i in c:
		bit += 1 << i - 1
	for i in range(1 << N):
		dp[i | bit] = min(dp[i | bit], dp[i] + a)
print(dp[-1] if dp[-1] != INF else -1)


def main():
	(n, m) = map(int, input().split())
	p = 2 ** n
	inf = 10 ** 9
	dp = [inf] * p
	dp[0] = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		c = sum([2 ** (int(j) - 1) for j in list(input().split())])
		for k in range(p):
			if dp[k | c] > dp[k] + a:
				dp[k | c] = dp[k] + a
	if dp[-1] == inf:
		print(-1)
	else:
		print(dp[-1])
main()


(n, m) = list(map(int, input().split()))
inf = 10 ** 9
cost = [inf for i in range(m)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	c = [int(x) - 1 for x in input().split()]
	s = 0
	for j in c:
		s |= 1 << j
	cost[i] = [s, a]
dp = [inf] * (1 << n)
dp[0] = 0
for s in range(1 << n):
	for (bit, c) in cost:
		dp[s | bit] = min(dp[s | bit], dp[s] + c)
print(-1 if dp[-1] == inf else dp[-1])


(n, m) = map(int, input().split())
ans = [float('inf')] * 2 ** n
ans[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	tmp = 0
	for j in c:
		tmp += 2 ** (j - 1)
	na = ans.copy()
	for j in range(2 ** n):
		if ans[j | tmp] > na[j] + a:
			ans[j | tmp] = na[j] + a
if ans[2 ** n - 1] == float('inf'):
	print(-1)
else:
	print(ans[2 ** n - 1])


INF = 10 ** 6
(n, m) = map(int, input().split())
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	bit = ['0'] * n
	for x in set(map(int, input().split())):
		bit[x - 1] = '1'
	bit = int(''.join(bit), 2)
	for j in range(2 ** n - 1, -1, -1):
		dp[j | bit] = min(dp[j | bit], a + dp[j])
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
a = []
b = []
c = []
MY_INF = 1000000007
for _ in range(M):
	(a_tmp, b_tmp) = map(int, input().split())
	a.append(a_tmp)
	b.append(b_tmp)
	c.append(list(map(int, input().split())))
c_bin = []
for i in range(M):
	c_bin.append(sum([1 << cij - 1 for cij in c[i]]))
memo = [None] * (1 << N)

def dp(state):
	nonlocal MY_INF
	if state == (1 << N) - 1:
		return 0
	if memo[state] != None:
		return memo[state]
	rets = [MY_INF]
	for i in range(M):
		if state | c_bin[i] > state:
			rets.append(a[i] + dp(state | c_bin[i]))
	ret = min(rets)
	memo[state] = ret
	return ret
ans = dp(0)
if ans != MY_INF:
	print(ans)
else:
	print(-1)


def main():
	(n, m) = map(int, input().split())
	a = [0] * m
	c = [0] * m
	INF = 10 ** 9
	dp = [INF] * 2 ** n
	for i in range(m):
		a[i] = int(input().split()[0])
		c[i] = sum([1 << int(i) - 1 for i in input().split()])
	dp[0] = 0
	for i in range(2 ** n):
		for (cos, pat) in zip(a, c):
			npat = i | pat
			if dp[npat] > cos + dp[i]:
				dp[npat] = cos + dp[i]
	if dp[2 ** n - 1] == INF:
		print(-1)
	else:
		print(dp[2 ** n - 1])

def __starting_point():
	main()
__starting_point()


from itertools import product
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
can_open = []
cost = []
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	cost.append(a)
	can_open.append(sum((1 << c - 1 for c in map(int, input().split()))))
n_bit = 1 << n
INF = 10 ** 18
dp = [INF] * n_bit
dp[0] = 0
for (j, (x, y)) in product(list(range(n_bit)), list(zip(can_open, cost))):
	m = j | x
	z = dp[j] + y
	if dp[m] > z:
		dp[m] = z
print(dp[-1] if dp[-1] != INF else -1)


INF = float('inf')
(N, M) = map(int, input().split())
dp = [INF for _ in range(2 ** N)]
dp[0] = 0
for i in range(M):
	(a, _) = map(int, input().split())
	(*C,) = map(int, input().split())
	open_bit = 0
	for i in C:
		open_bit |= 1 << i - 1
	for i in range(2 ** N):
		temp = dp[i] + a
		if dp[i | open_bit] > temp:
			dp[i | open_bit] = temp
print(dp[-1] if dp[-1] != INF else -1)


(N, M) = map(int, input().split())
keys = []
for _ in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	s = 0
	for cc in c:
		cc -= 1
		s |= 1 << cc
	keys += [(s, a)]
dp = [float('inf')] * (1 << N)
dp[0] = 0
for s in range(1 << N):
	for i in range(M):
		t = s | keys[i][0]
		dp[t] = min(dp[t], keys[i][1] + dp[s])
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


import sys
import itertools
(N, M) = map(int, input().split())
AB = []
C = []
for _ in range(M):
	AB.append(tuple(map(int, input().split())))
	C.append(sum((1 << int(x) - 1 for x in map(int, input().split()))))
INF = 10 ** 18
dp = [INF] * (1 << N)
dp[0] = 0
for (n, ((a, b), c)) in itertools.product(range(1 << N), zip(AB, C)):
	m = n | c
	x = dp[n] + a
	if dp[m] > x:
		dp[m] = x
ans = dp[-1]
if ans == INF:
	ans = -1
print(ans)


(N, M) = map(int, input().split())
r = [0] + [10 ** 9] * (2 ** N - 1)
for i in range(M):
	(a, _) = map(int, input().split())
	c = map(int, input().split())
	x = 0
	for e in c:
		x += 1 << e - 1
	for j in range(2 ** N):
		r[x | j] = min(r[x | j], r[j] + a)
print(r[-1] if r[-1] < 10 ** 9 else -1)


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 8)

def main():
	(N, M) = map(int, input().split())
	keys = []
	for _ in range(M):
		(a, b) = map(int, input().split())
		bits = sum([1 << i - 1 for i in map(int, input().split())])
		keys.append([a, bits])
	dp = [INF] * (2 ** N + 10)
	dp[0] = 0
	for i in range(M):
		for j in range(2 ** N):
			dp[j | keys[i][1]] = min(dp[j | keys[i][1]], dp[j] + keys[i][0])
	print(dp[2 ** N - 1] if dp[2 ** N - 1] != INF else -1)

def __starting_point():
	main()
__starting_point()


(N, M) = [int(_) for _ in input().split()]
AS = []
for _ in range(M):
	(a, _) = [int(_) for _ in input().split()]
	s = sum((1 << c - 1 for c in [int(_) for _ in input().split()]))
	AS += [(a, s)]
dp = [10 ** 10] * (1 << N)
dp[0] = 0
for S in range(1 << N):
	for (a, s) in AS:
		dp[S | s] = min(dp[S | s], dp[S] + a)
if dp[-1] == 10 ** 10:
	print(-1)
else:
	print(dp[-1])


(n, m) = list(map(int, input().split()))
keys = []
for _ in range(m):
	(cost, types) = list(map(int, input().split()))
	to_open = list(map(int, input().split()))
	keys.append([cost, to_open])
DP = [10 ** 9] * 2 ** n
DP[0] = 0
for (cost, to_open) in keys:
	openable = 0
	for open in to_open:
		openable |= 1 << open - 1
	for opened in range(2 ** n):
		pattern = opened | openable
		DP[pattern] = min(DP[pattern], DP[opened] + cost)
full_open = 2 ** n - 1
ans = DP[full_open]
if ans == 10 ** 9:
	ans = -1
print(ans)


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
INF = 10 ** 10
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(M):
	(a, b) = map(int, readline().split())
	c = list(map(int, readline().split()))
	key = 0
	for j in range(len(c)):
		key += 1 << c[j] - 1
	for j in range(len(dp)):
		if dp[j] == INF:
			continue
		if j | key == j:
			continue
		dp[j | key] = min(dp[j | key], dp[j] + a)
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
dp = [2 ** 63] * 4096
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	mask = 0
	c = list(map(int, input().split()))
	for i in c:
		mask |= 1 << i - 1
	nxtdp = dp[:]
	for j in range(1 << n):
		if dp[j] < 2 ** 63:
			nxtdp[j | mask] = min(nxtdp[j | mask], dp[j] + a)
	dp = nxtdp
print(dp[(1 << n) - 1] if dp[(1 << n) - 1] < 2 ** 63 else -1)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, m) = list(map(int, input().split()))
	keys = []
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		C = list(map(int, input().split()))
		s = 0
		for c in C:
			s |= 1 << c - 1
		keys.append([a, s])
	dp = [f_inf] * (1 << n)
	dp[0] = 0
	for now in range(1 << n):
		for (cost, key) in keys:
			nxt = now | key
			dp[nxt] = min(dp[nxt], dp[now] + cost)
	print(dp[-1] if dp[-1] != f_inf else -1)

def __starting_point():
	resolve()
__starting_point()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
INF = 10 ** 10
p = 2 ** N
dp = [INF] * p
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum([2 ** (i - 1) for i in map(int, input().split())])
	for i in range(p):
		dp[i | c] = min(dp[i] + a, dp[i | c])
if dp[-1] != INF:
	print(dp[-1])
else:
	print(-1)


def main():
	(n, m) = map(int, input().split())
	inf = 10 ** 9
	dp = [inf] * (1 << n)
	dp[0] = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		c = [1 << int(x) - 1 for x in input().split()]
		t = sum(c)
		for s in range(1 << n):
			if dp[t | s] > dp[s] + a:
				dp[t | s] = dp[s] + a
	print(-1 if dp[-1] == inf else dp[-1])

def __starting_point():
	main()
__starting_point()


(n, m) = [int(item) for item in input().split()]
INF = 10 ** 10
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = [int(item) for item in input().split()]
	c = [int(item) - 1 for item in input().split()]
	bit = 0
	for item in c:
		bit |= 1 << item
	for j in range(2 ** n):
		dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


def main():
	(n, m) = map(int, input().split())
	L = 2 ** n
	cost = [0] + [10 ** 8 for i in range(L - 1)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		c = sum(map(lambda x: 2 ** (int(x) - 1), input().split()))
		for i in range(L):
			q = c | i
			cost[q] = min(cost[q], cost[i] + a)
	print(cost[L - 1] if cost[L - 1] < 10 ** 8 else -1)
main()


def main():
	(N, M) = map(int, input().split())
	Inf = 10 ** 8
	dp = [Inf] * 2 ** N
	dp[0] = 0
	for i in range(M):
		(a, b) = map(int, input().split())
		tmp = list(map(int, input().split()))
		open_tresure = list((1 << j - 1 for j in tmp))
		op_tr = sum(open_tresure)
		for j in range(2 ** N):
			key = op_tr | j
			dp[key] = min(dp[key], dp[j] + a)
	if dp[-1] == Inf:
		print(-1)
	else:
		print(dp[-1])
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for _ in [0] * m:
	(a, b) = map(int, input().split())
	sc = 0
	for e in map(int, input().split()):
		sc += 1 << e - 1
	for i in range(1 << n):
		dp[i | sc] = min(dp[i | sc], dp[i] + a)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


import sys

def S():
	return sys.stdin.readline().rstrip()
(N, M) = map(int, S().split())
AB = []
C = []
for _ in range(M):
	AB.append(tuple((int(i) for i in S().split())))
	C.append(sum((1 << int(i) - 1 for i in S().split())))
dp = [10 ** 8 + 1] * (1 << N)
dp[0] = 0
for i in range(1 << N):
	for ((a, b), c) in zip(AB, C):
		dp[i | c] = min(dp[i | c], dp[i] + a)
if dp[-1] == 10 ** 8 + 1:
	print(-1)
else:
	print(dp[-1])


MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

def main():
	(N, M) = list(map(int, input().split()))
	key = []
	for _ in range(M):
		(a, b) = list(map(int, input().split()))
		c = list(map(int, input().split()))
		can_open = 0
		for i in c:
			can_open ^= 1 << i - 1
		key.append((a, can_open))
	dp = [[INF] * (1 << N) for _ in range(M + 1)]
	for i in range(M):
		dp[i][0] = 0
	for i in range(M):
		(price, can_open) = key[i]
		for s in range(1, 1 << N):
			dp[i + 1][s] = min(dp[i][s], dp[i][s & can_open ^ s] + price)
	print(dp[-1][-1] if dp[-1][-1] != INF else -1)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
dp = [0] * (2 ** n + 1)
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	temp = 0
	for i in c:
		temp += 2 ** (i - 1)
	for i in range(2 ** n):
		if i != 0 and dp[i] == 0:
			continue
		t = i | temp
		if dp[t] == 0:
			dp[t] = dp[i] + a
		else:
			dp[t] = min(dp[i] + a, dp[t])
ans = dp[2 ** n - 1]
if ans == 0:
	print(-1)
else:
	print(ans)


(N, M) = map(int, input().split())
dp = [float('inf')] * 2 ** N
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	key = 0
	for x in c:
		key += 2 ** (x - 1)
	ndp = dp.copy()
	for j in range(2 ** N):
		if dp[j | key] > ndp[j] + a:
			dp[j | key] = ndp[j] + a
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


from functools import reduce
(N, M) = map(int, input().split())
L = 1 << N
table = {0: 0}
for _ in range(M):
	(cost, _) = map(int, input().split())
	match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
	for (l, now) in table.copy().items():
		table[l | match] = min(now + cost, table.get(l | match, 10 ** 7))
print(table[L - 1] if table.get(L - 1, False) else -1)


(n, m) = map(int, input().split())
abcsl = []
for _ in range(m):
	(a, b) = map(int, input().split())
	cl = list(map(int, input().split()))
	abcsl.append((a, b, cl))
dp = [10 ** 9] * 2 ** n
dp[0] = 0
for (a, b, cl) in abcsl:
	b_bit = 0
	for c in cl:
		b_bit += 2 ** (c - 1)
	for i in range(2 ** n):
		dp[i | b_bit] = min(dp[i] + a, dp[i | b_bit])
if dp[2 ** n - 1] == 10 ** 9:
	print(-1)
else:
	print(dp[2 ** n - 1])


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, m) = list(map(int, input().split()))
	(A, C) = ([], [])
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		A.append(a)
		key = 0
		for c in map(int, input().split()):
			key |= 1 << c - 1
		C.append(key)
	dp = [f_inf] * (1 << n)
	dp[0] = 0
	for S in range(1 << n):
		for i in range(m):
			(key, cost) = (C[i], A[i])
			dp[S | key] = min(dp[S | key], dp[S] + cost)
	print(dp[-1] if dp[-1] != f_inf else -1)

def __starting_point():
	resolve()
__starting_point()


(N, M) = map(int, input().split())
box = [float('inf')] * 2 ** N
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	k = 0
	for i in c:
		k += 2 ** (i - 1)
	box[k] = min(box[k], a)
	for j in range(2 ** N):
		box[(k & j) + (k ^ j)] = min(box[(k & j) + (k ^ j)], box[k] + box[j])
if box[-1] == float('inf'):
	print(-1)
else:
	print(box[-1])


(n, m) = list(map(int, input().split()))
x = 2 ** n
dp = [1000000000 for _ in range(x)]
dp[0] = 0
for i in range(m):
	(ai, bi) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	bit = 0
	for j in range(bi):
		bit += 2 ** (c[j] - 1)
	for k in range(x):
		dp[k | bit] = min(dp[k | bit], dp[k] + ai)
if dp[x - 1] == 1000000000:
	print(-1)
else:
	print(dp[x - 1])


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
INF = 10 ** 8
dp = [INF] * ((1 << n) + 1)
dp[0] = 0
for i in range(m):
	(a, b) = list(map(int, input().split()))
	c = sum((1 << ci - 1 for ci in map(int, input().split())))
	for j in range(1 << n):
		if dp[j] + a < dp[j | c]:
			dp[j | c] = dp[j] + a
ans = -1 if dp[(1 << n) - 1] == INF else dp[(1 << n) - 1]
print(ans)


def solve(N, M, ABCi):
	inf = 10 ** 5 * 12 * 2
	for i in range(M):
		C = ABCi[i][2]
		ABCi[i][2] = sum([2 ** (c - 1) for c in C])
	dp = [[inf] * 2 ** N for _ in range(M + 1)]
	dp[0][0] = 0
	for i in range(1, M + 1):
		for j in range(2 ** N):
			(a, b, c) = ABCi[i - 1]
			dp[i][j] = min(dp[i - 1][c & j ^ j] + a, dp[i - 1][j])
	ans = min([x[2 ** N - 1] for x in dp])
	if ans == inf:
		ans = -1
	print(ans)

def __starting_point():
	(N, M) = list(map(int, input().split()))
	ABCi = [[int(i) for i in input().split()] + [[int(i) for i in input().split()]] for _ in range(M)]
	solve(N, M, ABCi)
__starting_point()


(n, m) = [int(x) for x in input().split()]
INF = int(1000000000.0 + 1)
dp = [INF] * (1 << n)
dp[0] = 0
for j in range(m):
	cost = int(input().split()[0])
	boxes = [int(x) - 1 for x in input().split()]
	mask = 0
	mask = sum((1 << box for box in boxes))
	for i in range(1 << n):
		if dp[i] + cost < dp[i | mask]:
			dp[i | mask] = dp[i] + cost
res = dp[-1] if dp[-1] != INF else -1
print(res)


(n, m) = map(int, input().split())
INF = 10 ** 7
p = 1 << n
dp = [INF] * p
dp[0] = 0
for _ in range(m):
	(a, _) = map(int, input().split())
	c = sum([1 << int(i) - 1 for i in input().split()])

	def k(s):
		dp[s | c] = dp[s] + a
	[k(s) for s in range(p) if dp[s | c] > dp[s] + a]
ans = dp[-1]
if ans == INF:
	ans = -1
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
L = []
PL = [2 ** x for x in range(N)]
for i in range(M):
	(cost, _) = map(int, input().split())
	k = sum([PL[i - 1] for i in map(int, input().split())])
	L.append((cost, k))
p = 2 ** N
dp = [10 ** 7] * p
dp[0] = 0
for i in range(M):
	(cost, k) = L[i]
	for j in range(p):
		m = j | k
		dp[m] = min(dp[m], dp[j] + cost)
print(dp[-1] if dp[-1] < 10 ** 7 else -1)


(n, m) = map(int, input().split())
dp = [float('INF')] * (1 << n)
dp[0] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	C = 0
	for e in c:
		C += 1 << e - 1
	for i in range(1 << n):
		dp[i | C] = min(dp[i | C], dp[i] + a)
if dp[-1] == float('INF'):
	print(-1)
else:
	print(dp[-1])


from collections import defaultdict
(N, M) = map(int, input().split())
a = []
c = []
dp = defaultdict(lambda : 1000000000)
for i in range(M):
	(ai, bi) = map(int, input().split())
	a.append(ai)
	c.append(sum([1 << int(ci) - 1 for ci in input().split()]))
dp[0] = 0
for i in range(M):
	for (k, v) in list(dp.items()):
		dp[k | c[i]] = min(dp[k | c[i]], dp[k] + a[i])
print(dp[(1 << N) - 1] if (1 << N) - 1 in dp else -1)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
inf = 10 ** 18
dp = [inf] * (1 << N)
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	Cs = list(map(int, input().split()))
	bb = 0
	for c in Cs:
		bb += 2 ** (c - 1)
	for x in range((1 << N) - 1, -1, -1):
		dp[bb | x] = min(dp[x] + a, dp[bb | x])
r = dp[(1 << N) - 1]
if r != inf:
	print(dp[(1 << N) - 1])
else:
	print(-1)


(n, m) = map(int, input().split())
dp = [0] + [10 ** 8 + 10] * (2 ** n - 1)
for i in range(m):
	(a, b) = map(int, input().split())
	s = sum([2 ** (x - 1) for x in list(map(int, input().split()))])
	for j in range(2 ** n):
		if dp[j | s] > dp[j] + a:
			dp[j | s] = dp[j] + a
if dp[-1] <= 10 ** 8:
	print(dp[-1])
else:
	print(-1)


(n, m) = map(int, input().split())
k = []
g = []
INF = float('inf')
for i in range(m):
	k.append(list(map(int, input().split()))[0])
	g.append(sum(map(lambda x: 2 ** (int(x) - 1), input().split())))
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(m):
	for j in range(2 ** n):
		dp[g[i] | j] = min(dp[g[i] | j], dp[j] + k[i])
print(-1 if dp[-1] == INF else dp[-1])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
INF = 10 ** 12
T = [2 ** i for i in range(N)]
dp = [INF] * 2 ** N
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	step = sum((T[c - 1] for c in C))
	for j in range(2 ** N):
		dp[step | j] = min(dp[step | j], dp[j] + a)
print(dp[-1] if dp[-1] < INF else -1)


import sys
input = sys.stdin.readline

def main():
	(N, M) = list(map(int, input().split()))
	A = [0] * M
	C = [0] * M
	for i in range(M):
		(A[i], _) = list(map(int, input().split()))
		C[i] = sum((2 ** (int(c) - 1) for c in input().split()))
	INF = 10 ** 18
	dp = [INF] * 2 ** N
	dp[0] = 0
	for (a, c) in zip(A, C):
		for s in range(2 ** N):
			dp[s | c] = min(dp[s | c], dp[s] + a)
	ans = dp[-1] if dp[-1] != INF else -1
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
D = [0] + [9 ** 9] * (1 << N)
for i in range(M):
	a = int(input().split()[0])
	s = sum((1 << ~-int(c) for c in input().split()))
	for j in range(1 << N):
		D[s | j] = min(D[s | j], D[j] + a)
print(D[-2] % 9 ** 9 or -1)


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	(n, m) = map(int, input().split())
	dp = [10 ** 10] * (1 << n)
	dp[0] = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		C = list(map(int, input().split()))
		d = 0
		for c in C:
			d |= 1 << c - 1
		for j in range(1 << n):
			dp[j | d] = min(dp[j | d], dp[j] + a)
	if dp[-1] == 10 ** 10:
		print(-1)
	else:
		print(dp[-1])

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
kagi = [[] for _ in range(m)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	X = list(map(int, input().split()))
	bit = 0
	for x in X:
		bit |= 2 ** (x - 1)
	kagi[i] = [a, bit]
ok = 2 ** n - 1
kagi.sort(key=lambda x: x[1])
zenkai = 2 ** n
dp = [float('inf')] * int(zenkai + 1)
dp[0] = 0
for i in range(2 ** n):
	if dp[i] == float('inf'):
		continue
	for j in range(m):
		s = i | kagi[j][1]
		dp[s] = min(dp[s], dp[i] + kagi[j][0])
if dp[zenkai - 1] == float('inf'):
	print(-1)
else:
	print(dp[zenkai - 1])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	(N, M) = MAP()
	dp = [INF] * (1 << N)
	dp[0] = 0
	for _ in range(M):
		(a, b) = MAP()
		c = LIST()
		tmp = 0
		for x in c:
			tmp = tmp | 1 << x - 1
		for S in range(1 << N):
			dp[S | tmp] = min(dp[S | tmp], dp[S] + a)
	print(dp[-1] if dp[-1] != INF else -1)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
from collections import defaultdict
INF = float('inf')
dic = defaultdict(lambda : INF)
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = 0
	for k in c:
		d |= 1 << k - 1
	dic[d] = min(dic[d], a)
dp = [INF] * (1 << N)
dp[0] = 0
for (k, v) in dic.items():
	for b in range((1 << N) - 1):
		if dp[b] == INF:
			continue
		if b == b | k:
			continue
		dp[b | k] = min(dp[b | k], dp[b] + v)
print(-1 if dp[-1] == INF else dp[-1])


(n, m) = map(int, input().split())
arr = []
for _ in range(m):
	(a, b) = map(int, input().split())
	tl = list(map(int, input().split()))
	tmp = 0
	for val in tl:
		tmp += 2 ** (val - 1)
	arr.append((a, tmp))
dp = [10 ** 18] * 2 ** n
dp[0] = 0
for (val, flag) in arr:
	for i in range(2 ** n - 1, -1, -1):
		if dp[i] == 10 ** 18:
			continue
		else:
			dp[i | flag] = min(dp[i | flag], dp[i] + val)
if dp[-1] == 10 ** 18:
	print(-1)
else:
	print(dp[-1])


import sys
input = sys.stdin.readline
inf = 10 ** 8
(n, m) = map(int, input().split())
A = []
C = []
dp = [inf] * (1 << n)
dp[0] = 0
for _ in range(m):
	(a, _) = map(int, input().split())
	c = list(map(int, input().split()))
	A.append(a)
	tmp = 0
	for i in c:
		tmp += 1 << i - 1
	C.append(tmp)
for i in range(1 << n):
	for (index, j) in enumerate(C):
		dp[i | j] = min(dp[i | j], dp[i] + A[index])
ans = dp[-1]
if ans == inf:
	ans = -1
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
INF = 10 ** 9
dp = [INF] * 2 ** N
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	bit = 0
	for i in c:
		bit |= 1 << i - 1
	for i in range(2 ** N):
		if dp[i | bit] > dp[i] + a:
			dp[i | bit] = dp[i] + a
if dp[-1] >= INF:
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
inf = 10 ** 12
ab = []
cs = []
for i in range(m):
	(a, b) = map(int, input().split())
	c = tuple(map(int, input().split()))
	ab.append((a, b))
	cs.append(c)
dp = [inf] * 2 ** n
dp[0] = 0
for i in range(m):
	x = 0
	for h in cs[i]:
		x += 2 ** (h - 1)
	for j in range(2 ** n):
		dp[j | x] = min(dp[j | x], dp[j] + ab[i][0])
print(dp[-1] if dp[-1] != inf else -1)


(n, m) = map(int, input().split())
a = [0] * m
b = [0] * m
c = [[] for i in range(m)]
for i in range(m):
	(a[i], b[i]) = map(int, input().split())
	c[i] = sum([2 ** (int(x) - 1) for x in input().split()])
dp = [1000000000 for i in range(2 ** n)]
dp[0] = 0
for i in range(2 ** n):
	for j in range(m):
		dp[i | c[j]] = min(dp[i | c[j]], dp[i] + a[j])
if dp[2 ** n - 1] == 1000000000:
	print(-1)
else:
	print(dp[2 ** n - 1])


(N, M) = map(int, input().split())
lst = [0] * M
for i in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = 0
	for n in range(b):
		d += 2 ** (c[n] - 1)
		lst[i] = (a, d)
ans = [[float('inf') for e in range(2 ** N)] for f in range(M + 1)]
ans[0][0] = 0
for j in range(M):
	for i in range(2 ** N):
		e = i - (lst[j][1] & i)
		ans[j + 1][i] = min(ans[j][e] + lst[j][0], ans[j][i])
if ans[M][2 ** N - 1] == float('inf'):
	print(-1)
else:
	print(ans[M][2 ** N - 1])


(N, M) = map(int, input().split())
pp = []
for _ in range(M):
	(a, b) = map(int, input().split())
	cc = map(int, input().split())
	bit = 0
	for c in cc:
		bit += 1 << c - 1
	pp.append((a, bit))
inf = 10000000
S = 1 << N
dp = [inf] * S
dp[0] = 0
for s in range(1, S):
	for (a, bit) in pp:
		dp[s] = min(dp[s], a + dp[s - (s & bit)])
if dp[S - 1] >= inf:
	print(-1)
else:
	print(dp[S - 1])


inf = float('inf')
(n, m) = map(int, input().split())
dp = [inf] * (1 << n)
dp[0] = 0
for _ in range(m):
	(cost, _) = map(int, input().split())
	c = (int(x) - 1 for x in input().split())
	mask = 0
	for k in c:
		mask |= 1 << k
	for b in range((1 << n) - 1):
		nb = b | mask
		dp[nb] = min(dp[nb], dp[b] + cost)
res = dp[(1 << n) - 1]
print(-1 if res == inf else res)


(N, M) = map(int, input().split())
INF = 10 ** 8
N_dp = 2 ** N
DP = [INF] * N_dp
DP[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	C = [int(i) for i in input().split()]
	c_bit = sum((2 ** (c - 1) for c in C))
	for i in range(N_dp):
		DP[c_bit | i] = DP[i] + a if DP[i] + a < DP[c_bit | i] else DP[c_bit | i]
if DP[-1] == INF:
	DP[-1] = -1
print(DP[-1])


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, m) = list(map(int, input().split()))
	ABC = []
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		C = list(map(int, input().split()))
		s = ['0'] * n
		for c in C:
			s[c - 1] = '1'
		c = ''.join(s[::-1])
		ABC.append([a, b, int(c, 2)])
	dp = [f_inf for _ in range(1 << n)]
	dp[0] = 0
	for (a, b, c) in ABC:
		for i in range(1 << n):
			idx = i | c
			dp[idx] = min(dp[idx], dp[i] + a)
	if dp[-1] == f_inf:
		print(-1)
	else:
		print(dp[-1])

def __starting_point():
	resolve()
__starting_point()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
dp = [float('inf')] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = sum((1 << i - 1 for i in map(int, input().split())))
	for j in range(2 ** n):
		if dp[c | j] > dp[j] + a:
			dp[c | j] = dp[j] + a
if dp[-1] == float('inf'):
	ans = -1
else:
	ans = dp[-1]
print(ans)


(N, M) = map(int, input().split())
p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
	(a, _) = map(int, input().split())
	c = sum((2 ** (i - 1) for i in map(int, input().split())))
	for x in range(p2):
		an = x | c
		table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
print(ans if ans != 10 ** 9 else -1)


(n, m) = map(int, input().split())
inf = 10 ** 10
dp = [inf for _ in range(2 ** n)]
dp[0] = 0
bin_s = [2 ** i for i in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	clst = list(map(int, input().split()))
	tmp = 2 ** n - 1
	for c in clst:
		tmp -= bin_s[c - 1]
	for i in range(2 ** n):
		dp[i] = min(dp[i], dp[i & tmp] + a)
if dp[-1] == inf:
	print(-1)
else:
	print(dp[-1])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
(N, M) = MAP()
key_lis = []
key_cost = []
for _ in range(M):
	(a, b) = MAP()
	c = LIST()
	key = 0
	for x in c:
		key += 2 ** (x - 1)
	key_lis.append(key)
	key_cost.append(a)
dp = [INF] * (1 << N)
dp[0] = 0
for S in range(1 << N):
	for (i, key) in enumerate(key_lis):
		dp[S | key] = min(dp[S | key], dp[S] + key_cost[i])
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	(n, m) = map(int, input().split())
	price = [0] * m
	typesnum = [0] * m
	keybit = [0] * m
	for i in range(m):
		(price[i], typesnum[i]) = map(int, input().split())
		keybit[i] = sum(map(lambda x: 2 ** (int(x) - 1), input().split()))
	dp = [10 ** 9] * (1 << n)
	dp[0] = 0
	for bit in range(1 << n):
		for i in range(m):
			dp[bit | keybit[i]] = min(dp[bit | keybit[i]], dp[bit] + price[i])
	if dp[-1] == 10 ** 9:
		dp[-1] = -1
	print(dp[-1])

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
dp = [float('inf')] * ((1 << n) + 1)
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c_list = list(map(int, input().split()))
	c = 0
	for j in range(b):
		c += 1 << c_list[j] - 1
	for j in range(1 << n):
		dp[j | c] = min(dp[j] + a, dp[j | c])
if dp[(1 << n) - 1] == float('inf'):
	ans = -1
else:
	ans = dp[(1 << n) - 1]
print(ans)


(N, M) = map(int, input().split())
dp = [float('inf')] * 2 ** N
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum([2 ** (int(i) - 1) for i in input().split()])
	for s in range(2 ** N):
		t = s | c
		if dp[t] > dp[s] + a:
			dp[t] = dp[s] + a
ans = dp[-1]
if dp[-1] == float('inf'):
	print(-1)
else:
	print(ans)


import sys

def solve():
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	Dist = [10 ** 20] * pow(2, N)
	Dist[0] = 0
	for _ in range(M):
		(a, b) = map(int, input().split())
		C = [int(c) for c in input().split()]
		binaryC = 0
		for c in C:
			binaryC += pow(2, c - 1)
		for (j, d) in enumerate(Dist):
			if d < 10 ** 20:
				Dist[j | binaryC] = min(Dist[j | binaryC], Dist[j] + a)
	print(Dist[-1] if Dist[-1] < 10 ** 20 else -1)
	return 0

def __starting_point():
	solve()
__starting_point()


def main():
	import numpy as np
	(n, m) = list(map(int, input().split()))
	dp = np.full(2 ** n, 10 ** 9, dtype=np.int64)
	dp[0] = 0
	opened = np.arange(2 ** n)
	for _ in range(m):
		(cost, types) = list(map(int, input().split()))
		to_open = np.array(list(map(int, input().split())), dtype=np.int64)
		openable = np.left_shift(1, to_open - 1).sum()
		new_indexes = opened | openable
		new_costs = dp + cost
		sort_index = np.argsort(new_costs)
		new_costs.sort()
		(update_pattern, idx) = np.unique(new_indexes[sort_index], return_index=True)
		update_cost = new_costs[idx]
		dp[update_pattern] = np.minimum(dp[update_pattern], update_cost)
	full_open = 2 ** n - 1
	ans = dp[full_open]
	if ans == 10 ** 9:
		ans = -1
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
p = 1 << n
dp = [float('inf')] * p
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = sum([1 << j - 1 for j in list(map(int, input().split()))])
	for k in range(p):
		if dp[k | c] > dp[k] + a:
			dp[k | c] = dp[k] + a
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
dp = [float('inf')] * 2 ** N
dp[0] = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum((1 << i - 1 for i in map(int, input().split())))
	for x in range(2 ** N):
		dp[c | x] = min(dp[c | x], dp[x] + a)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
N2 = 2 ** N
INF = float('inf')
X = [INF] * N2
X[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	k = sum((1 << c - 1 for c in C))
	for j in range(N2):
		if X[j | k] > X[j] + a:
			X[j | k] = X[j] + a
ans = X[-1]
if ans >= INF:
	ans = -1
print(ans)


(n, m) = map(int, input().split())
inf = 10 ** 9
dp = [0] + [inf] * ((1 << n) - 1)
for _ in range(m):
	newdp = [p for p in dp]
	(a, b) = map(int, input().split())
	c = sum((1 << int(i) - 1 for i in input().split()))
	for bits in range(len(dp)):
		newdp[bits | c] = min(newdp[bits | c], dp[bits] + a)
	dp = newdp
print(-1 if dp[-1] == inf else dp[-1])


(n, m) = map(int, input().split())
a = [None] * m
c = [0] * m
for i in range(m):
	(a[i], b) = map(int, input().split())
	ls = list(map(int, input().split()))
	for j in ls:
		c[i] |= 1 << j - 1
n2 = 1 << n
dp = [1000000000.0] * n2
dp[0] = 0
for i in range(m):
	for S in range(n2):
		if dp[S | c[i]] > dp[S] + a[i]:
			dp[S | c[i]] = dp[S] + a[i]
if dp[n2 - 1] < 1000000000.0:
	print(dp[n2 - 1])
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
inf = 10 ** 9 + 7
dp = [inf] * 2 ** n
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	C = list(map(int, input().split()))
	bit = 0
	for i in C:
		bit |= 1 << i - 1
	for j in range(2 ** n):
		dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] >= inf:
	print(-1)
else:
	print(dp[-1])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
ks = []
for _ in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	T = 0
	for ci in c:
		T += 1 << ci - 1
	ks.append((a, T))
dp = [10 ** 18] * (1 << N)
dp[0] = 0
for S in range(1 << N):
	for (a, T) in ks:
		dp[S | T] = min(dp[S | T], dp[S] + a)
if dp[-1] == 10 ** 18:
	print(-1)
else:
	print(dp[-1])


INF = float('inf')
(n, m) = map(int, input().split())
a = [0] * m
c = [0] * m
for i in range(m):
	(a[i], _) = map(int, input().split())
	c[i] = sum(map(lambda x: 2 ** (int(x) - 1), input().split()))
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(m):
	for j in range(2 ** n):
		dp[c[i] | j] = min(dp[c[i] | j], dp[j] + a[i])
print(-1 if dp[-1] == INF else dp[-1])


(n, m) = map(int, input().split())
inf = 10 ** 9
dp = [inf for _ in range(2 ** n)]
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	d = sum((1 << i - 1 for i in map(int, input().split())))
	for j in range(2 ** n):
		jord = j | d
		dp[jord] = min(dp[jord], dp[j] + a)
if dp[-1] == inf:
	print(-1)
else:
	print(dp[-1])


INF = 10 ** 9
(n, m) = list(map(int, input().split()))
keys = []
for _ in range(m):
	(a, _) = list(map(int, input().split()))
	c = 0
	for i in input().split():
		c += 2 ** (int(i) - 1)
	keys.append((a, c))
dp = [INF] * 2 ** n
dp[0] = 0
for (a, c) in keys:
	tmp = [INF] * 2 ** n
	for (j, d) in enumerate(dp):
		if d == INF:
			continue
		if d < tmp[j]:
			tmp[j] = d
		if d + a < tmp[j | c]:
			tmp[j | c] = d + a
	dp = tmp
print(dp[-1] if dp[-1] < INF else -1)


(n, m) = map(int, input().split())
L = 2 ** n
cost = [0] + [10 ** 8 for i in range(L - 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	c = sum([2 ** (int(i) - 1) for i in input().split()])
	for j in range(L):
		q = j | c
		x = cost[j] + a
		if cost[q] > x:
			cost[q] = x
print(cost[L - 1] if cost[L - 1] < 10 ** 8 else -1)


(n, m) = map(int, input().split())
dp = [float('inf') for i in range(2 ** n)]
dp[0] = 0
keys = []
for i in range(m):
	(a, b) = map(int, input().split())
	cs = list(map(int, input().split()))
	key = 0
	for c in cs:
		key += 2 ** (c - 1)
	dp[key] = a
	keys.append((key, a))
keys.sort()
for i in range(2 ** n):
	for (key, a) in keys:
		if dp[i | key] > dp[i] + a:
			dp[i | key] = dp[i] + a
print(dp[-1] if dp[-1] != float('inf') else -1)


(n, m) = map(int, input().split())
x = [None for _ in range(m)]
for i in range(m):
	(a, b) = map(int, input().split())
	c = map(int, input().split())
	t = sum(map(lambda x: 2 ** (x - 1), c))
	x[i] = (a, t)
INF = 10 ** 9
dp = [INF for _ in range(2 ** n)]
dp[0] = 0
for (ai, ti) in x:
	for j in range(2 ** n):
		dp[ti | j] = min(dp[ti | j], dp[j] + ai)
if dp[-1] >= INF:
	ans = -1
else:
	ans = dp[-1]
print(ans)


def f(L):
	X = 0
	for k in L:
		X += 2 ** (k - 1)
	return X
(N, M) = map(int, input().split())
H = 2 ** N
inf = float('inf')
DP = [inf for _ in range(H)]
DP[0] = 0
for _ in range(M):
	(A, B) = map(int, input().split())
	C = f(list(map(int, input().split())))
	for k in range(H):
		DP[k | C] = min(DP[k | C], DP[k] + A)
if DP[-1] == inf:
	print(-1)
else:
	print(DP[-1])


(n, m) = map(int, input().split())
inf = 10 ** 18
cost = [inf for _ in range(2 ** n)]
cost[0] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	key = 0
	for i in range(b):
		key += 2 ** (c[i] - 1)
	for t in range(2 ** n):
		cost[t | key] = min(cost[t | key], cost[t] + a)
ans = cost[-1]
if ans < inf:
	print(ans)
else:
	print(-1)


INF = 10 ** 8
(N, M) = map(int, input().split())
n = 2 ** N
dp = [0] + [INF] * (n - 1)
for _ in range(M):
	(a, b) = map(int, input().split())
	c = sum(map(lambda x: 2 ** (x - 1), list(map(int, input().split()))))
	for i in range(n):
		dp[i | c] = min(dp[i] + a, dp[i | c])
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


import sys
(n, m) = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__
for _ in [0] * m:
	(a, b) = map(int, sys.stdin.readline().split())
	s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
	for t in range(1 << n):
		if dp[t] == -1:
			continue
		dp[t | s] = min(dp[t | s], dp[t] + a)
print(dp[-1] if dp[-1] != INF else -1)


import sys
input = sys.stdin.readline

def inpl():
	return list(map(int, input().split()))
(N, M) = inpl()
size = 2 ** N
F = [2 ** i for i in range(12)]
DP = [10 ** 18] * size
DP[0] = 0
for _ in range(M):
	(a, b) = inpl()
	X = sum([F[i - 1] for i in inpl()])
	for i in range(size):
		DP[i | X] = min(DP[i | X], DP[i] + a)
if DP[-1] == 10 ** 18:
	print(-1)
else:
	print(DP[-1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
ma = 1 << n
DP = [float('inf')] * ma
DP[0] = 0
for i in range(m):
	nxt = DP[:]
	(a, b) = map(int, input().split())
	mask = 0
	for c in map(int, input().split()):
		mask += 1 << c - 1
	for j in range(ma):
		if nxt[j | mask] > DP[j] + a:
			nxt[j | mask] = DP[j] + a
	DP = nxt
ans = DP[-1]
if ans == float('inf'):
	ans = -1
print(ans)


(n, m) = map(int, input().split(' '))
dp = [10 ** 9 for _ in range(2 ** n)]
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split(' '))
	c = list(map(int, input().split(' ')))
	num = 0
	for j in range(b):
		num += 1 << c[j] - 1
	for s in range(2 ** n):
		if dp[s | num] >= dp[s] + a:
			dp[s | num] = dp[s] + a
if dp[-1] == 10 ** 9:
	print(-1)
else:
	print(dp[-1])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
ALL = 1 << N
dp = [10 ** 9] * ALL
dp[0] = 0
for i in range(M):
	ndp = dp[:]
	(a, b) = map(int, input().split())
	c = [int(i) - 1 for i in input().split()]
	C = 0
	for i in c:
		C |= 1 << i
	for S in range(ALL):
		ndp[S | C] = min(ndp[S | C], dp[S] + a)
	dp = ndp
if dp[-1] == 10 ** 9:
	print(-1)
else:
	print(dp[-1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
e = [(int(input().split()[0]), list(map(int, input().split()))) for _ in range(m)]
INF = 10 ** 18
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(2 ** n):
	if dp[i] >= INF:
		continue
	for (a, c) in e:
		bit = i
		for j in c:
			bit |= 2 ** (n - j)
		dp[bit] = min(dp[bit], dp[i] + a)
a = dp[-1]
if a >= INF:
	print(-1)
else:
	print(dp[-1])


def solve():
	(N, M) = map(int, input().split())
	DP = [float('inf')] * 2 ** N
	DP[0] = 0
	for i in range(M):
		(A, B) = map(int, input().split())
		keys = sum((1 << int(i) - 1 for i in input().split()))
		for j in range(2 ** N):
			DP[j | keys] = min(DP[j | keys], DP[j] + A)
	return DP[-1] if DP[-1] != float('inf') else -1
print(solve())


def solve():
	ans = 0
	(N, M) = map(int, input().split())
	(A, C) = ([0] * M, [0] * M)
	for i in range(M):
		(A[i], b) = map(int, input().split())
		c = list(map(int, input().split()))
		for j in range(b):
			C[i] += 1 << c[j] - 1
	dp = [float('inf')] * (1 << N)
	dp[0] = 0
	for i in range(1, (1 << N) + 1):
		for key in range(M):
			if C[key] & i == 0:
				continue
			dp[i] = min(dp[i], dp[i & ~C[key]] + A[key])
	ans = dp[-1]
	if ans == float('inf'):
		return -1
	return ans
print(solve())


(N, M) = list(map(int, input().split()))
A = []
min_state = [10 ** 9] * 2 ** N
min_state[0] = 0
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	key = 0
	for tmp in c:
		key += 2 ** (tmp - 1)
	A.append((a, key))
L = len(min_state)
for (a, key) in A:
	for (i, score) in enumerate(min_state):
		next_key = key | i
		if min_state[next_key] > score + a:
			min_state[next_key] = score + a
if min_state[-1] == 10 ** 9:
	print(-1)
else:
	print(min_state[-1])


def chmin(l, i, v):
	if l[i] > v:
		l[i] = v
		return True
	return False

def main():
	(N, M) = map(int, input().split())
	keys = []
	for i in range(M):
		(a, b) = map(int, input().split())
		C = map(int, input().split())
		mask = 0
		for c in C:
			mask |= 1 << c - 1
		keys.append((a, mask))
	patterns = 1 << N
	INF = float('inf')
	dp = [INF] * patterns
	dp[0] = 0
	for (a, mask) in keys:
		for i in range(patterns):
			chmin(dp, i | mask, dp[i] + a)
	ans = dp[patterns - 1]
	print(-1 if ans == INF else ans)

def __starting_point():
	main()
__starting_point()


(N, M) = list(map(int, input().split()))
inf = 10 ** 10
dp = [[inf] * 2 ** N for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
	(a, b) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	s = 0
	for cc in c:
		s += 2 ** (cc - 1)
	for j in range(2 ** N):
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
		dp[i + 1][j | s] = min(dp[i + 1][j | s], dp[i][j] + a)
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] < inf else -1)


I = lambda : list(map(int, input().split()))
(n, m) = I()
e = eval('(I()[0],I()),' * m)
dp = [9000000000.0] * 2 ** n
dp[0] = 0
for i in range(2 ** n):
	if dp[i] == 9000000000.0:
		continue
	for (a, c) in e:
		b = i
		for j in c:
			b |= 2 ** (n - j)
		dp[b] = min(dp[b], dp[i] + a)
print(-(dp[-1] == 9000000000.0) or dp[-1])


(N, M) = map(int, input().split())
L = 2 ** N
l = [float('inf')] * L
l[0] = 0
r = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048)
for i in range(M):
	s = 0
	(a, b) = map(int, input().split())
	c = tuple(map(int, input().split()))
	for j in c:
		s += r[j - 1]
	for j in range(L):
		l[j | s] = min(l[j | s], l[j] + a)
if l[-1] == float('inf'):
	print(-1)
else:
	print(l[-1])


import sys
input = lambda : sys.stdin.readline().rstrip()
inpl = lambda : list(map(int, input().split()))
(N, M) = inpl()
P = 2 ** N
INF = 10 ** 12
cost = [INF] * P
cost[0] = 0
for _ in range(M):
	(a, b) = inpl()
	c = inpl()
	k = 0
	for ci in c:
		k |= 1 << ci - 1
	for i in range(P):
		new = i | k
		cost[new] = min(cost[new], cost[i] + a)
ans = cost[P - 1]
if ans >= INF:
	print(-1)
else:
	print(ans)


(n, m) = [int(j) for j in input().split()]
dp = [10 ** 8] * 2 ** n
dp[0] = 0
cost = []
for i in range(m):
	(x, y) = [int(j) for j in input().split()]
	tmp = [int(j) for j in input().split()]
	ind = 0
	for j in tmp:
		ind |= 1 << j - 1
	cost.append((ind, x))
for i in range(1 << n):
	for j in range(m):
		dp[i | cost[j][0]] = min(dp[i | cost[j][0]], dp[i] + cost[j][1])
if dp[-1] != 10 ** 8:
	print(dp[-1])
else:
	print(-1)


(n, m) = [int(_) for _ in input().split()]
k = []
for i in range(m):
	k.append([int(_) for _ in input().split()])
	k[-1].append([int(_) for _ in input().split()])
dp = [10 ** 9 for _ in range(2 ** n)]
dp[0] = 0
for i in range(m):
	id = 0
	for j in range(k[i][1]):
		id += 2 ** (k[i][2][j] - 1)
	for j in range(2 ** n):
		dp[j | id] = min(dp[j | id], dp[j] + k[i][0])
if dp[-1] == 10 ** 9:
	print(-1)
else:
	print(dp[-1])


(N, M) = map(int, input().split())
newcount = [float('inf') for _ in range(2 ** N)]
newcount[0] = 0
for k in range(M):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	bit = 0
	for k in range(b):
		bit += 2 ** (c[k] - 1)
	count = tuple(newcount)
	for k in range(2 ** N):
		now = bit | k
		newcount[now] = min(newcount[now], a + count[k])
count = newcount
if count[-1] < 10 ** 6:
	print(count[-1])
else:
	print(-1)


(n, m) = map(int, input().split())
cost = [0] * m
keys = [0] * m
for i in range(m):
	(a, b) = map(int, input().split())
	cost[i] = a
	k = list(map(int, input().split()))
	for j in range(b):
		keys[i] |= 1 << k[j] - 1
INF = 10 ** 9 + 1
dp = [INF] * 2 ** n
dp[0] = 0
for i in range(len(keys)):
	for j in range(len(dp) - 1, -1, -1):
		if dp[j] != INF:
			dp[j | keys[i]] = min(dp[j | keys[i]], dp[j] + cost[i])
if dp[-1] != INF:
	print(dp[-1])
else:
	print(-1)


MAX = 10 ** 8 + 1
(N, M) = map(int, input().split())
X = [MAX] * 2 ** N
X[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	k = sum((1 << c - 1 for c in map(int, input().split())))
	for (j, x) in enumerate(X):
		if X[j | k] > x + a:
			X[j | k] = x + a
print(X[-1] if X[-1] < MAX else -1)


(n, m) = map(int, input().split())
dp = [10 ** 9] * (1 << n)
dp[0] = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	key = 0
	for i in map(int, input().split()):
		key += 1 << i - 1
	for i in range(1 << n):
		dp[i | key] = min(dp[i | key], dp[i] + a)
if dp[-1] > 10 ** 8:
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
dp = [10 ** 20] * (1 << n)
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	bit = 0
	for j in c:
		bit |= 1 << j - 1
	for j in range(1 << n):
		dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == 10 ** 20:
	print(-1)
else:
	print(dp[-1])


(n, m) = map(int, input().split())
dp = [float('inf') for _ in range(2 ** n)]
dp[0] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	k = 0
	p = 1
	for x in c:
		k += 2 ** (x - 1)
	for j in range(2 ** n):
		L = j | k
		dp[L] = min(dp[L], dp[j] + a)
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


(f, *L) = open(0).readlines()
(n, m) = map(int, f.split())
t = [(int(a.split()[0]), list(map(int, b.split()))) for (a, b) in zip(*[iter(L)] * 2)]
K = []
for (a, C) in t:
	r = 0
	for c in C:
		r |= 2 ** (c - 1)
	K.append((a, r))
INF = float('inf')
dp = [INF] * 2 ** n
dp[0] = 0
for g in range(2 ** n):
	for (a, c) in K:
		if dp[g | c] > dp[g] + a:
			dp[g | c] = dp[g] + a
print(-1 if dp[-1] == INF else dp[-1])


(n, m) = map(int, input().split())
g = 1 << n
dp = [10 ** 18] * g
dp[0] = 0
for i in range(m):
	(a, s) = map(int, input().split())
	f = 0
	for k in map(int, input().split()):
		f += 1 << k - 1
	for j in range(g - 1, -1, -1):
		dp[j | f] = min(dp[j] + a, dp[j | f])
print(-1 if dp[-1] == 10 ** 18 else dp[-1])


(N, M) = map(int, input().split())
b_cnt = 2 ** N
INF = 10 ** 9
dp = [INF] * b_cnt
dp[0] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	c = sum([2 ** (int(x) - 1) for x in list(input().split())])
	for j in range(b_cnt):
		if dp[j | c] > dp[j] + a:
			dp[j | c] = dp[j] + a
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


import sys

def solve():
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	L = pow(2, N)
	Dist = [10 ** 20] * L
	Dist[0] = 0
	for _ in range(M):
		(a, b) = map(int, input().split())
		bit = 0
		C = [int(c) for c in input().split()]
		for c in C:
			bit += pow(2, c - 1)
		for k in range(L):
			if Dist[k] < 10 ** 20:
				Dist[k | bit] = min(Dist[k | bit], Dist[k] + a)
	if Dist[L - 1] == 10 ** 20:
		print(-1)
	else:
		print(Dist[L - 1])
	return 0

def __starting_point():
	solve()
__starting_point()


def main():
	(N, M) = map(int, input().split())
	inf = 10 ** 9
	p = 1 << N
	dp = [inf] * p
	dp[0] = 0
	for i in range(M):
		(a, b) = map(int, input().split())
		C = list(map(int, input().split()))
		c_bit = sum([1 << c - 1 for c in C])
		for j in range(p):
			dp[j | c_bit] = min(dp[j | c_bit], dp[j] + a)
	if dp[p - 1] == inf:
		print(-1)
	else:
		print(int(dp[p - 1]))

def __starting_point():
	main()
__starting_point()


(n, m) = [int(i) for i in input().split()]
dp = [[float('inf') for i in range(2 ** n)] for j in range(m + 1)]
dp[0][0] = 0
for i in range(m):
	(a, _) = [int(_) for _ in input().split()]
	c = sum([2 ** (int(_) - 1) for _ in input().split()])
	for j in range(2 ** n):
		dp[i + 1][j | c] = min(dp[i][j | c], dp[i][j] + a, dp[i + 1][j | c])
		dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
print([dp[-1][-1], -1][dp[-1][-1] == float('inf')])