Problem:
 Score : 500 points    Problem Statement 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 1 2 3
10 1
1
15 1
2
30 2
1 2      Sample Output 1 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.       Sample Input 2 12 1
100000 1
2      Sample Output 2 -1  We cannot unlock all the boxes.       Sample Input 3 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      Sample Output 3 69942

Solution (Python):
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])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))



N, M = lr()
keys = [None] * M
for i in range(M):
    a, b = lr()
    C = lr()
    bit = 0
    for c in C:
        bit += 1 << (c-1)
    keys[i] = (a, bit)

INF = 10 ** 9
dp = [INF] * 2 ** N 
dp[0] = 0
for key in keys:
    a, bit = key
    for i in range(2 ** N):
        dp[i|bit] = min(dp[i|bit], dp[i] + a)

print(-1 if dp[-1] == INF else dp[-1])

Solution (Python):
N,M=map(int,input().split())
key=[]
cost=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append(s)
    cost.append(a)

node=2**N

dp=[[10**10 for i in range(0,node)] for j in range(0,M)]

for i in range(0,M):
    dp[i][node-1]=0

for i in range(0,M):
    for j in range(1,node):
        k=node-1-j
        if i==0:
            if k|key[0]==node-1:
                dp[0][k]=cost[0]
        else:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k|key[i]]+cost[i])

if dp[M-1][0]>=10**10:
    print(-1)
else:
    print(dp[M-1][0])

Solution (Python):
INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = 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)

Solution (Python):
N, M = map(int, input().split())

dp = [float('inf')] * (1 << N)
dp[0] = 0

u = 1 << N
for i in range(M):
    a, b = map(int, input().split())
    c = sum(1 << (x - 1) for x in map(int, input().split()))

    for j in range(u):
        dp[c | j] = min(dp[c | j], dp[j] + a)


if dp[-1] != float('inf'):
    print(dp[-1])
else:
    print(-1)

Solution (Python):

n, m = map(int, input().split())
inf = 10 ** 10
keys = [0 for _ in range(m)]
A = [] 

for i in range(m):
    a, _ = map(int, input().split())
    keys[i] = sum([2 ** (int(c) - 1) for c in input().split()])
    A.append(a)
    
dp = [[inf for _ in range(2 ** n)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(0, m):
    for key in range(2 ** n):
        dp[i+1][key] = dp[i][key]
        
    for key in range(2 ** n):
        dp[i+1][key | keys[i]] = min(dp[i+1][key | keys[i]],
                                     dp[i][key] + A[i])

if dp[m][2 ** n - 1] == inf:
    print(-1)
else:
    print(dp[m][2 ** n - 1])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):


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)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int,input().split())
key = [0] * M
cost = [0] * M
for i in range(M):
    a, b = map(int,input().split())
    cost[i] = a
    key_id = list(map(int,input().split()))
    for j in range(b):
        key[i] |= (1 << (key_id[j] - 1))
dp = [[float("inf")] * (1<<N)] * (M + 1)
dp[0][0] = 0
for i in range(M):
    for j in range(1<<N):
        if dp[i + 1][j | key[i]] > dp[i][j] + cost[i]:
            dp[i + 1][j | key[i]] = dp[i][j] + cost[i]
        if dp[i + 1][j] > dp[i][j]:
            dp[i + 1][j] = dp[i][j]
if dp[-1][-1] == float("inf"):
    print(-1)
else:
    print(dp[-1][-1])

Solution (Python):

N, M = map(int, input().rstrip().split())
INF = int(1e18)

abc = []
for _ in range(M):
    a, b = map(int, input().rstrip().split())
    c = list(map(int, input().rstrip().split()))
    abc.append([a, b, c])
    

dp = [[INF] * 2 ** (N + 1) for _ in range(2)]

for i in range(M):
    mask = 0
    for c in abc[i][2]:
        mask += 2 ** (c - 1)

    for j in range(2 ** (N + 1)):
        dp[i%2][j] = dp[(i+1)%2][j]

    dp[i%2][mask] = min(dp[i%2][mask], abc[i][0])
        
    for j in range(2 ** (N + 1)):
        if dp[(i+1)%2][j] != INF:
            dp[i%2][j|mask] = min(dp[i%2][j|mask], dp[(i+1)%2][j] + abc[i][0])
    
if dp[i%2][2**N-1] == INF:
    print(-1)
else:
    print(dp[i%2][2**N-1])

Solution (Python):

n, m = map(int, input().split())

lists = []
for i in range(m):
    price, num = map(int, input().split())
    K = list(map(int, input().split()))
    cnt = 0
    for some in K:
        cnt += 2**(n - some)
    lists.append((price, cnt))

dp = [[10**10 for i in range(2**n)]for j in range(m + 1)]

dp[0][0] = 0
for i in range(1, m + 1):
    price, mode = lists[i - 1][0], lists[i - 1][1]
    for j in range(2**n):
        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j &(2**n-1-mode)] + price)

ans = dp[m][2**n - 1]

if ans < 10**10:
    print(ans)
else:
    print(-1)

Solution (Python):
n,m = map(int, input().split())
a=[]
c=[]
for i in range(m):
    tmp,_=map(int, input().split())
    a.append(tmp)
    tmp=list(map(int, input().split()))
    bit = 0
    for b in tmp:
        bit+=(1<<(b-1))
    c.append(bit)

dp = [[10**9 for i in range(2**n)] for j in range(m+1)]
dp[0][0]=0

for i in range(m):
    cst = a[i]
    key=c[i]
    for s in range(2**n):
        dp[i+1][s] = min(dp[i+1][s], dp[i][s])
        dp[i+1][s|key] = min(dp[i+1][s|key], dp[i][s]+cst)

ans=dp[-1][-1]
if ans ==10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
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):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
items = []
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    c_ = sum([1 << (x - 1) for x in c])
    items.append([a, c_])

dp = [[float("inf")]*2**n for _ in range(m + 1)]
for i in range(m + 1):
    dp[i][0] = 0

for i in range(1, m + 1):
    a, c_ = items[i - 1]
    
    for j in range(2**n):
        dp[i][j] = dp[i - 1][j]
    
    for j in range(2**n):
        dp[i][j|c_] = min(dp[i][j|c_], dp[i - 1][j] + a)

ans = float("inf")

for i in range(1, m + 1):
    ans = min(ans, dp[i][-1])

if ans != float("inf"):
    print(ans)
else:
    print(-1)

Solution (Python):
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,_=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)

if __name__ == '__main__':
    main()

Solution (Python):
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,_=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)

if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):





n, m = map(int, input().split())
A, B, C = [], [], []
for _ in range(m):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    c = list(map(int, input().split()))
    now = 0
    for i in range(b-1, -1, -1):
        now += 2**(c[i]-1)
    C.append(now)

INF = 10**9
DP = [[INF for _ in range(2**n)] for _ in range(m+1)]
DP[0][0] = 0

for i in range(m):
    for j in range(2**n):
        c = C[i]
        
        DP[i+1][j] = min(DP[i][j], DP[i+1][j])
        
        nex = j | c
        DP[i+1][nex] = min(DP[i+1][nex], DP[i][j]+A[i])

ans = 10**9
for i in range(m):
    ans = min(DP[i][-1], ans)

if ans == 10**9:
    ans = -1

print(ans)

Solution (Python):
inf=10**9
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
dp=[[inf]*(2**n) for _ in range(m+1)]
def two(i):
	return "0"*(n-len(bin(i)[2:]))+bin(i)[2:]
for i in range(m+1):
	dp[i][0]=0
for i in range(m):
	a,b=map(int,input().split())
	r=0
	c=list(map(int,input().split()))
	for p in c:
		r+=2**(p-1)
	for j in range(2**n):
		x=j|r
		dp[i+1][x]=min(dp[i][j]+a,dp[i][x],dp[i+1][x])
	for j in range(2**n):
		dp[i+1][j]=min(dp[i+1][j],dp[i][j])
print(dp[-1][-1]) if dp[-1][-1]!=inf else print(-1)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
def main():
    N, M = MAP()
    dp = [INF] * (1<<N)
    dp[0] = 0

    for i in range(M):
        a, b = MAP()
        c = LIST()
        d = 0
        
        for x in c:
            
            d += 1<<(x-1)
        for j in range(1<<N): 
    
            tmp = j|d
            dp[tmp] = min(dp[tmp], dp[j] + a)
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
def main():
    INF=10**9
    n,m=map(int,input().split())
    key=[0]*m
    keycost=[0]*m

    for i in range(m):
        a,b=map(int,input().split())
        keycost[i]=a
        c=[pow(2,int(i)-1) for i in input().split()]
        key[i]=sum(c)
    
    dp=[[INF]*(m+1) for _ in range(1<<n)]
    dp[0]=[0]*(1+m)
    
    for s in range(1<<n):
        for i in range(m):
            dp[s][i+1]=min(dp[(s&key[i])^s][i]+keycost[i],dp[s][i])
    
    if dp[-1][m]==INF:
        print(-1)
    else:
        print(dp[-1][m])
 
if __name__=='__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0]*M
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C[m] = [int(cm) for cm in input().split()]

INF = 100000000
dp = [[INF] * 2**N for _ in range(M + 1)]
dp[0][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in range(2**N):
        pre_bit = next_bit = bit
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in range(2**N):
        pre_bit = bit
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

if dp[-1][-1] == INF:
    print(-1)
else:
    print(dp[-1][-1])

Solution (Python):
N, M = (int(i) for i in input().split())
cos = [0] * M
bit = [0] * M
for i in range(M):
    a, b = (int(j) for j in input().split())
    cos[i] = a
    c = [int(j) for j in input().split()]
    bit[i] = sum([2 ** (j-1) for j in c])

DP = [[float("inf")] * 2**N for counter1 in range(M+1)]
for i in range(M):
    DP[i][0] = 0

for i in range(M):
    a = cos[i]
    bi = bit[i]
    for j in range(2**N):
        DP[i+1][j|bi] = min(DP[i+1][j|bi], DP[i][j] + a)
        DP[i+1][j] = min(DP[i+1][j], DP[i][j])

ans = DP[M][2**N-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Solution (Python):
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])

Solution (Python):
n,m = list(map(int,input().split()))

dp = [1e9 for _ in range(2**n)]


dp[0] = 0
for i in range(1,m+1):
  a, _ = list(map(int,input().split()))
  C = list(map(int,input().split()))
  s = sum([2**(c-1) for c in C]) 
  for j in range(2**n): 
    dp[j|s] = min(dp[j|s], dp[j] + a)  

ans = dp[2**n-1] 
print(ans if ans < 1e9 else -1)

Solution (Python):
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)

Solution (Python):
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):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)

Solution (Python):
def main():
    n, m = map(int, input().split())
    keys = [[None for j in range(2)] for i in range(m)]
    for i in range(m):
        a, b = map(int, input().split())
        keys[i][0] = a
        keys[i][1] = 0
        c = list(map(int, input().split()))
        for j in c:
            keys[i][1] += int(pow(2, j-1))
    dp = [10**9 for i in range(int(pow(2, n)))]
    dp[0] = 0
    for i in range(int(pow(2, n))):
        for j in range(m):
            if dp[i | keys[j][1]] > dp[i] + keys[j][0]:
                dp[i | keys[j][1]] = dp[i] + keys[j][0]
    if dp[int(pow(2, n)) - 1] == 10**9:
        print("-1")
    else:
        print(dp[int(pow(2, n)) - 1])

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    S = []
    for i in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        s = 0
        for c in C:
            c -= 1
            s |= (1 << c)
        S.append((a,s))

    dp = [float('inf')] * (1 << N)
    dp[0] = 0
    for i in range(1 << N):
        for j in range(M):
            t = i | S[j][1]
            dp[t] = min(dp[t], dp[i] + S[j][0])

    if dp[(1<<N)-1] == float('inf'):
        print(-1)
    else:
        print(dp[(1<<N)-1])
    
if __name__ == "__main__":
    main()

Solution (Python):











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**(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
print(dp[-1] if dp[-1]!=inf else -1)

Solution (Python):
import sys
input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d

infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)

Solution (Python):
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**(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
print(dp[-1] if dp[-1]!=inf else -1)

Solution (Python):
n, m = map(int, input().split())
keys = []

for _ in range(m):
    cost, types = 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 i in range(2 ** n):
        pattern = i | openable
        DP[pattern] = min(DP[pattern], DP[i] + cost)

ans = DP[2**n - 1]

if ans == 10 ** 9:
    ans = -1

print(ans)

Solution (Python):
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = min(a,dp[m])
dp[0] = 0
for i in range(1<<N):
  for j in range(1<<N):
    dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Solution (Python):
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = a
dp[0] = 0
for i in range(M):
  for j in range(1<<N):
    a,m = ls[i]
    dp[m|j] = min(dp[m|j], a+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
bit_cnt = 2 ** N 
INF = 10 ** 10
dp = [INF] * bit_cnt
dp[0] = 0
for _ in range(M):
    price, b = lr()
    open = sum([2 ** (x-1) for x in lr()]) 
    for j in range(bit_cnt):
        if dp[j|open] > dp[j] + price:
            dp[j|open] = dp[j] + price

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
n, m = map(int, input().split())

A = [0]*m
C = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    cs = list(map(int, input().split()))
    c = 0
    for c_ in cs:
        c += 1 << (c_-1)
    C[i] = c

dp = [float('inf')]*(1 << n)
dp[0] = 0
for i in range(1 << n):
    for j in range(m):
        c = C[j]
        dp[i|c] = min(dp[i|c], dp[i]+A[j])

if dp[-1] != float('inf'):
    print(dp[-1])
else:
    print(-1)

Solution (Python):
import sys
import itertools
input = sys.stdin.readline


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


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    K = []
    for _ in range(M):
        a, _ = read_values()
        T = read_list()
        K.append((a, T))

    dp = [10 ** 8] * (2 ** N + 10)
    dp[0] = 0
    for a, T in K:
        k = 0
        for t in T:
            k += 1 << (t - 1)
        for i in range(2 ** N):
            dp[i | k] = min(dp[i | k], dp[i] + a) 

    res = dp[2 ** N - 1]
    print(res if res != 10 ** 8 else -1)

if __name__ == "__main__":
    main()

Solution (Python):


n, m = map(int, input().split())

dp = [[float("inf") for _ in range(2 ** n)] for i in range(m + 1)]
dp[0][0] = 0

pattern = {0}

for i in range(1, m+1):
  ai, bi = map(int, input().split()) 
  ci_bit = sum(2 ** (cij - 1) for cij in map(int, input().split()))
  new_pattern = set()
  for j in pattern:
    dp[i][j | ci_bit] = min(dp[i][j | ci_bit], dp[i-1][j] + ai)
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    new_pattern.add(j | ci_bit)
  pattern |= new_pattern


print(-1 if dp[m][2**n - 1] == float("inf") else dp[m][2**n - 1])

Solution (Python):
N, M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(list(map(int, input().split())))
    C.append(list(map(int, input().split())))

INF = 10 ** 9 + 7
dp = [INF] * (2 ** N)
dp[0] = 0

for i, ((a, b), c) in enumerate(zip(AB, C)):
    num = int("".join(["01"[int(i + 1 in c)] for i in range(N)]), 2)
    for j in range(2 ** N):
        dp[j | num] = min(dp[j | num], dp[j] + a)

print(dp[-1] if dp[-1] < INF else -1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M = MI()
	dp = [float("inf")] * (2**N)
	dp[0] = 0
	for _ in range(M):
		a,b = MI()
		cc = LI()
		state = 0
		for c in cc:
			c -= 1
			state += (1 << c)
		for i in range(2**N):
			if(dp[i]!=float("inf")):
				dp[i|state] = min(dp[i|state], dp[i]+a)
	if(dp[-1]!=float("inf")):
		print(dp[-1])
	else:
		print(-1)


main()

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = [[]for _ in range(M)]
    C = [0]*M
    for i in range(M):
        A[i], b = LI()
        c = LI()
        for j in range(b):
            C[i] += 2**(c[j]-1)
    loop = 2**N
    dp = [[inf]*loop for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for l in range(loop):
            dp[i + 1][l] = min(dp[i + 1][l],dp[i][l])
            next = l|C[i]
            if next==l:
                continue
            dp[i+1][next] = min(dp[i+1][next],dp[i][l] + A[i])
    ans = dp[M][loop-1]
    if ans==inf:
        print(-1)
    else:
        print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Solution (Python):
from bisect import *
N,M=map(int,input().split())
kagi=[]
for i in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    value=0
    for i in range(b):
        C[i]-=1
        value+=2**C[i]

    kagi.append([a,value])


dp=[[10**8 for i in range(2**N)] for m in range(M+1)]
dp[0][0]=0
for i in range(M):
    for s in range(2**N):
        dp[i+1][s]=min(dp[i][s],dp[i+1][s])
        dp[i+1][s|kagi[i][1]]=min(dp[i+1][s|kagi[i][1]],dp[i][s]+kagi[i][0])
if 10**8==dp[M][-1]:
    print(-1)
else:
    print(dp[M][-1])

Solution (Python):
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])

Solution (Python):
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    dp = [float("inf")]*(2**N)
    S = [sum([2**(c - 1) for c in abc[2:]]) for abc in ABC]
    dp[0] = 0
    for i in range(M):
        for bit in range(2**N):
            result = int(bit | S[i])
            dp[result] = min(dp[result],dp[bit] + ABC[i][0])        
    print(dp[2**N - 1] if dp[2**N - 1] < float("inf") else -1)
    return

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    c = tuple(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=0
        for k in j:
            v+=2**(k-1)
        dp[i|v] = min(dp[i|v], dp[i]+cost)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)

Solution (Python):
def main():
    N, M  = map(int, input().split())
    l = []
    for i in range(M):
        a, b = map(int, input().split())
        c = map(int, input().split())
        k = sum(2 ** (i-1) for i in c)
        l.append((a, k))
    m = [float('inf')] * (2 ** N)
    m[0] = 0
    for i in range(M):
        for j in range(2 ** N):
            m[j | l[i][1]] = min(m[j | l[i][1]], m[j] + l[i][0])
    if m[-1] == float('inf'):
        print('-1')
    else:
        print(m[-1])
main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
n,m = map(int, input().split())
key = []
tmp = 0
for i in range(m):
    a,b = map(int, input().split())
    c = 0
    for i in map(int, input().split()):
        c += 1<<(i-1)
    key.append((a,c))
    tmp |= c
   
inf = float('INF')
flag = False
opened = 2**n
if tmp != opened -1:
    print(-1)
    exit()
dp = [inf for i in range(opened)]
dp[0] = 0
for a,c in key:
    for i in range(opened):
        if dp[i] + a < dp[i | c]:
            dp[i | c] = dp[i] + a

print(dp[opened-1] if dp[opened-1] else -1)

Solution (Python):
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(1 << n):
    if dp[i] == INF:
        continue
    for next_cost, next_key in zip(cost, keys):
        m = next_key | i
        dp[m] = min(dp[m], dp[i] + next_cost)

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
keys = []
for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (c - 1) for c in list(map(int, input().split()))])
    keys.append([a, c])



dp = [float('inf')] * (1 << N)
dp[0] = 0

for i, (cost, key) in enumerate(keys):
    for bs in range(1 << N):
        dp[bs | key] = min(dp[bs | key], dp[bs] + cost)

print(dp[-1] if dp[-1] != float('inf') else -1)

Solution (Python):
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)

Solution (Python):
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
for i in range(M):
    a, b = map(int, input().split())
    C = map(int, input().split())
    A[i] = a
    K[i] = sum([2 ** (i - 1) for i in C])


INF = (1 << 32) - 1
dp = [INF] * (2 ** N)
dp[0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    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)