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())
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) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    for j in range(2 ** N):
        here = dp[i][j]
        dp[i + 1][j] = min(dp[i + 1][j], here)
        dp[i + 1][j | k] = min(dp[i + 1][j | k], dp[i][j | k], here + a)

ans = dp[M][2 ** N - 1] if dp[M][2 ** N - 1] < INF else -1
print(ans)

Solution (Python):
import sys
INF = sys.maxsize
N,M = map(int,input().split(" "))
tmp = []
for _ in range(M):
    a,b = map(int,input().split(" "))
    bit = 0
    nums = map(int,input().split(" "))
    for n in nums:
        bit += 2**(n-1)
    tmp.append((a,bit))

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

for i in range(M):
    a,bit = tmp[i]
    for j in range(2**N):
        cover = bit | j
        dp[cover] = min(dp[cover], dp[j] + a)

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

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

def main():
    N,M = map(int,input().split())
    INF = 10**7
    k = []
    for _ in range(M):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        bit = 0
        for i in c:
            bit += 2**(i-1)
        k.append((a,bit))
    dp = [INF for _ in range(1<<N)]
    dp[0] = 0
    for i in range(M):
        a,bit = k[i]
        for j in range(1<<N):
            af = bit|j
            dp[af] = min(dp[af],dp[j]+a)
            
    print(dp[-1] if dp[-1] != INF else -1)
if __name__ == "__main__":
    main()

Solution (Python):

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)

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

key = [0 for i in range(M)]
cost = []

for i in range(M):
    a,b = list(map(int,input().split()))
    c = list(map(int,input().split()))
    cost.append(a)
    for j in range(b):
        key[i] += pow(2,c[j]-1)

INF = float('inf')

DP = [[INF]*(2**N) for i in range(M+1)]
DP[0][0] = 0
for i in range(M):
    for j in range(2**N):
        DP[i+1][j] = min(DP[i][j],DP[i+1][j])
        DP[i+1][j|key[i]] = min(DP[i+1][j|key[i]],DP[i][j]+cost[i],DP[i][j|key[i]])

if DP[M][2**N-1]>10**27:
    print(-1)
else:
    print(DP[M][2**N - 1])

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
a = []
b = []
for i in range(m):
    aa,bb = inm()
    cc = inl()
    a.append(aa)
    x = 0
    for j in range(bb):
        x += 2**(cc[j]-1)
    b.append(x)

ddprint(a)
ddprint(b)

t = [BIG]*(2**n)
t[0] = 0
for i in range(m):
    for j in range(2**n-1):
        if t[j]<BIG:
            t[j|b[i]] = min(t[j|b[i]], t[j]+a[i])
if t[2**n-1]==BIG:
    print(-1)
else:
    print(t[2**n-1])

Solution (Python):



N,M = map(int, input().split())
ab = []
c = []
for _ in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
    tmp = tuple(map(int, input().split()))
    bit_c = 0
    
    for i in tmp:
        bit_c = bit_c | (1 << (i - 1))

    c.append(bit_c)

INF = 10**9

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


for bit in range(1 << N):
    for i in range(M):
        dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + ab[i][0])

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

Solution (Python):
n, m = map(int, input().split())
abc = []
for i in range(m):
    a, b = map(int, input().split())
    c_ = list(map(int, input().split()))
    c = 0
    for v in c_:
        c += 2**(v-1)
    abc.append([a, b, c])

INF = 10**9
dp = [[INF for _ in range(1 << n)]for _ in range((m+1))]

for i in range(m):
    dp[i][0] = 0

for i in range(m):
    for j in range(1 << n):
        s = j | abc[i][2]
        dp[i+1][s] = min(dp[i+1][s], dp[i][j] + abc[i][0])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
if dp[-1][-1] == INF:
    print(-1)
else:
    print(dp[-1][-1])

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ab = []
c = []
def bit(ls):
    res = 0
    for elem in ls:
        res += 2**(elem-1)
    return res

for i in range(M):
    ab.append(list(map(int,input().split())))
    l = list(map(int,input().split()))
    val = bit(l)
    c.append(val)
dp = [10**6]*(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]+ab[i][0])
if dp[2**N-1] == 10**6:
    print(-1)
else:
    print(dp[2**N-1])

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

Solution (Python):


import sys
input = sys.stdin.readline

N,M = map(int,input().split())
lis = []
for _ in range(M):
    a,b = map(int,input().split())
    C = list(map(int,input().split()))
    s = 0
    for c in C:
        s |= 1 << (c-1) 
    
    lis.append((s,a))

dp = [float("inf")]*(2**N)  
dp[0] = 0

for bit in range(2**N):
    for i in range(M):
        s,a = lis[i]
        t = bit | s
        dp[t] = min(dp[t],dp[bit]+a)

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

Solution (Python):




N,M=map(int,input().split())

dp=[10**9]*2**N

dp[0]=0

for _ in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    cl=["0"]*N
    for item in c:
        cl[item-1]="1"
    plus=int(str("".join(cl)),2)
    for i in range(len(dp))[::-1]:
        if dp[i]!=10**9:
            
            dp[i|plus]=min(dp[i|plus],dp[i]+a)
if dp[-1]!=10**9:
    print(dp[-1])
else:
    print(-1)

Solution (Python):
N, M = map(int,input().split())
A = []
C = []
for i in range(M):
  a, b = map(int,input().split())
  c = list(map(int, input().split()))
  tmp = 0
  for cc in c:
    tmp += 2 ** (cc - 1)
  A.append(a)
  C.append(tmp)



INF = 10 ** 15
dp = [INF for _ in range(2 ** N)]
dp[0] = 0

for i in range(M):
  for j in range(2 ** N - 1, -1, -1):
    if dp[j] != INF:
      dp[j | C[i]] = min(dp[j | C[i]], dp[j] + A[i])
      
print(dp[-1] if dp[-1] != INF else -1)

Solution (Python):
from itertools import product
N,M = map(int,input().split())
G = {i:[] for i in range(M)}
for i in range(M):
    a,b = map(int,input().split())
    G[i] = [a,list(map(int,input().split()))]
INFTY = 10**11
dp = [[INFTY for S in range(2**N)] for _ in range(M+1)]
for j in range(M+1):
    dp[j][0] = 0
for j in range(M):
    for S in range(2**N):
        y = 0
        for x in G[j][1]:
            y += 2**(x-1)
        dp[j+1][S] = min(dp[j][S],dp[j][S&(~y)]+G[j][0])
a =dp[M][2**N-1]
if a>=INFTY:
    print(-1)
else:
    print(a)

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

Solution (Python):




N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
A=[0]*(m+1); S=[0]*m

for i in range(m):
    a,b=map(int,input().split())
    A[i]=a
    s=0
    for ci in map(int,input().split()):
        s|=1<<(ci-1)
    S[i]=s
dp=[[inf]*(2**n) for i in range(m+1)]
for i in range(m+1):
    dp[i][0]=0


for i in range(m):
    for s in range(2**n):
        dp[i+1][s]=min(dp[i+1][s],dp[i][s])
        
        
        
        dp[i+1][s|S[i]]=min(dp[i+1][s|S[i]],dp[i][s|S[i]],dp[i][s]+A[i])
print(dp[m][(1 << n)-1] if dp[m][(1 << n)-1] != inf else -1)

Solution (Python):
N,M = map(int, input().split())
key = []
key_i = []
for i in range(M):
  key.append(list(map(int, input().split())))
  key_i.append(list(map(int, input().split())))
keybin = [0]*M
for j in range(M):
  for x in key_i[j]:
    keybin[j] += 2**(x-1)
INF = float("inf")
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):
    x = keybin[i-1]
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    DP[i][j|x] = min(DP[i][j|x],DP[i-1][j|x], DP[i-1][j]+key[i-1][0])
if DP[-1][-1] >10**18:
  print(-1)
else:
  print(DP[-1][-1])

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
ab=[]
c=[]
li=[0]*n
for i in range(m):
    ab.append(list(map(int,input().split())))
    c.append(list(map(int,input().split())))
    for j in range(len(c[i])):
        li[c[i][j]-1]+=1
if min(li)==0:
    print(-1)
    exit()
dp=[[float('inf')]*(2**n) for i in range(2)]
for i in range(2):
    dp[i][0]=0

li=[]
for i in range(m):
    tmp=0
    for j in range(ab[i][1]):
        tmp+=2**(c[i][j]-1)
    li.append(tmp)



for i in range(m):
    for j in range(2**n):
        
        
        dp[i+1][j|li[i]]=min(dp[i+1][j|li[i]],dp[i+1][j]+ab[i][0])
        dp.append(dp[-1])
print(dp[-1][-1])

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
LE = 1 << N
DP = [10**15]*(LE)
DP[0] = 0

for _ in range(M):
    a,b=LI()
    key = 0
    for i in LI():
        key |= 1<<(i-1)
    for j in range(LE):
        DP[j | key] = min(DP[j | key], DP[j] + a)

res = DP[(1 << N) - 1]
print(res if res != 10**15 else -1)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
LE = 1 << N
DP = [10**15]*(LE)
DP[0] = 0

for _ in range(M):
    a,b=LI()
    key = 0
    for i in LI():
        key |= 1<<(i-1)
    for j in range(LE):
        DP[j | key] = min(DP[j | key], DP[j] + a)

res = DP[(1 << N) - 1]
print(res if res != 10**15 else -1)

Solution (Python):
N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [inf for i in range(2**N)]
dp[0] = 0
for i in range(1,M+1):
    dp[C[i]] = min(dp[C[i]],A[i])
    for j in range(2**N):
        k =  j|C[i]
        dp[k] = min(dp[k],dp[j]+A[i])
if dp[2**N-1] == inf:
    dp[2**N-1] = -1
print(dp[2**N-1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = []
    c = []
    for i in range(m):
        d,b = LI()
        e = LI_()
        a.append(d)
        t = 0
        for u in e:
            t |= 2**u
        c.append(t)

    d = collections.defaultdict(lambda: inf)
    d[0] = 0
    for i in range(m):
        ai = a[i]
        ci = c[i]
        for k,v in list(d.items()):
            nk = k | ci
            nv = v + ai
            if d[nk] > nv:
                d[nk] = nv
    if d[2**n-1] == inf:
        return -1

    return d[2**n-1]


print(main())

Solution (Python):
n, m = map(int, input().split())
S = [] 
C = [] 
for _ in range(m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  C.append(a)
  s = sum([2 ** (i - 1) for i in c])
  S.append(s)


INF = 10 ** 19
dp = [INF] * (1 << n) 
dp[0] = 0
for s, c in zip(S, C):
  for i in range(1 << n):
    j = i | s 
    x = dp[i] + c
    dp[j] = min(dp[j], x)
    
ans = dp[-1]
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [[INF]*(2**n) for i in range(m+5)]
for i in range(m+1):
    dp[i][0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for j in range(2**n):
        dp[i+1][j] = min(dp[i][j], dp[i][j&(~key)]+val)
        
res = dp[m][2**n-1]
print(res if res != INF else -1)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [INF]*(2**n)
dp[0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for _ in range(2**n):
        dp[_|key] = min(dp[_|key], dp[_]+val)
        
res = dp[-1]
print(res if res != INF else -1)

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

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    md = pow(2, n)
    dp = [10 ** 15] * md
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, readline().split()))
        c = sum([2 ** (v - 1) for v in list(map(int, readline().split()))])
        for j in range(md):
            dp[j | c] = min(dp[j | c], dp[j] + a)
    print(dp[-1] if dp[-1] != 10 ** 15 else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())







L = []
v = 0
for _ in range(M):
    a, b = map(int, input().split())
    l = sum([1 << (int(v) - 1) for v in input().split()])
    L.append([a, b, l])
    v = v | l
if v != (1 << N) - 1:
     print(-1)
     exit()

dp = [[10 ** 18 for _ in range(1 << N)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
     for j in range(1 << N):
          dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

          dp[i + 1][j | L[i][2]] =  min(dp[i + 1][j | L[i][2]], dp[i][j] + L[i][0])

print(dp[M][(1 << N) - 1])

Solution (Python):
N,M=map(int,input().split())
a=[0]*(M+1)
b=[0]*(M+1)
c=[[] for _ in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))

 
d=[0]*M
for i in range(M):
    for cij in c[i]:
        d[i]+=pow(2,cij-1)

inf=10**9

dp = [[inf]*pow(2,N) for _ in range(M+1)]


for i in range(M+1):
    dp[i][0] = 0


for i in range(M):
    for j in range(pow(2,N)):
        dp[i+1][j|d[i]] =min(dp[i+1][j|d[i]] , dp[i][j]+a[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a,b=[0]*M,[0]*M
    c=[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
        l=list(map(int,input().split()))
        for box in l:
            c[i]=c[i]|(1<<(box-1))
    dp=[[INF]*(2**N) for _ in range(M+1)]
    dp[0][0]=0
    for i in range(M):
        for boxes in range(2**N):
            dp[i+1][boxes]=min(dp[i+1][boxes],dp[i][boxes])
            dp[i+1][boxes|c[i]]=min(dp[i+1][boxes|c[i]],dp[i][boxes]+a[i])
    print(dp[M][2**N-1] if dp[M][2**N-1]!=INF else -1)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
a = []
b = []
c = []

import sys
sys.setrecursionlimit(2000)

for i in range(M):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    ci = list(map(int, input().split()))
    c.append(ci)

c_bin = [0] * M
for j in range(M):
    for k in range(b[j]):
        c_bin[j] |= (1 << (c[j][k] - 1))

ceil = 1 << N
memo = [None] * (ceil * (M + 1))

def dp(pos, state):
    global M, ceil
    idx = pos * ceil + state
    
    if state == ceil - 1:
        ret = 0
    elif pos == M:
        ret = -1
    elif memo[idx] != None:
        return memo[idx]
    else:
        ret0 = dp(pos + 1, (state | c_bin[pos]))
        ret1 = dp(pos + 1, state)
        if ret0 == ret1 == -1:
            ret = -1
        elif ret1 == -1:
            ret = a[pos] + ret0
        else:
            ret = min(a[pos] + ret0, ret1)
    
    memo[idx] = ret
    return ret

print(dp(0, 0))

Solution (Python):
def solve():
    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(lambda x: int(x) - 1, input().split()))
        open = 0
        for i in range(b):
            open += 1 << c[i]
        for i in range(2 ** N):
            if dp[i] + a <= dp[i | open]:
                dp[i | open] = dp[i] + a
    
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import product
def main():
    N, M = map( int, input().split())
    costs = [0]*M
    keys = [0]*M
    for i in range(M):
        costs[i], b = map( int, input().split())
        C = list( map( int, input().split()))
        key = 0
        for c in C:
            key += pow(2, c-1)
        keys[i] = key
    K = pow(2,N)
    dp =[10**7]*K
    dp[0] = 0
    for i in range(M):
        key = keys[i]
        cost = costs[i]
        for j in range(K):
            if j != (j | key):
                if dp[j] + cost < dp[j|key]:
                    dp[j|key] = dp[j] + cost
    if dp[K-1] == 10**7:
        print(-1)
    else:
        print(dp[K-1])
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product
def main():
    N, M = map( int, input().split())
    costs = [0]*M
    keys = [0]*M
    for i in range(M):
        costs[i], b = map( int, input().split())
        C = list( map( int, input().split()))
        key = 0
        for c in C:
            key += pow(2, c-1)
        keys[i] = key
    K = pow(2,N)
    dp =[10**7]*K
    dp[0] = 0
    for i in range(M):
        key = keys[i]
        cost = costs[i]
        for j in range(K):
            if j != (j | key):
                if dp[j] + cost < dp[j|key]:
                    dp[j|key] = dp[j] + cost
    if dp[K-1] == 10**7:
        print(-1)
    else:
        print(dp[K-1])
if __name__ == '__main__':
    main()

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

bitdp = [[float('inf') for i in range(1<<n)] for i in range(m+1)]
   
bitdp[0][0] = 0

for i in range(m):
   for j in range(1<<n):
      bitdp[i+1][j] = min(bitdp[i][j], bitdp[i+1][j])
      bitdp[i+1][j|abl[i][1]] = min(bitdp[i][j] + abl[i][0], bitdp[i][j|abl[i][1]], bitdp[i+1][j|abl[i][1]])

if bitdp[-1][(1<<n)-1] == float('inf'):
   print(-1)
else:
   print(bitdp[-1][(1<<n)-1])

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

cost = []
open = []
for i in range(m):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    cost.append(a)
    open.append(c)

dp = [10**7] * (2**n)
dp[0] = 0
for i in range(m):
    key = []
    for j in range(1, n+1):
        if j in open[i]:
            key.append("1")
        else:
            key.append("0")
    key = "".join(key)
    key = int(key, 2)
    for j in range(2**n):
        next = j | key
        dp[next] = min(dp[next], dp[j] + cost[i])

if dp[2**n-1] == 10**7:
    print(-1)
else:
    print(dp[2**n-1])

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

    n, m = map(int, input().split())
    ab = []
    c = []

    for i in range(m):
        ab.append(list(map(int, input().split())))
        c.append(list(map(int, input().split())))

    for i in range(m):
        temp = 0
        for j in range(len(c[i])):
            temp += 2**(c[i][j]-1)
        c[i] = temp
        

    dp = dict()

    for i in range(2**n):
        dp[i] = 10**9
        

    dp[0] = 0

    
    for i in range(m):
        for k, item in dp.items():
            dp[c[i] | k] = min(dp[c[i] | k], dp[k]+ab[i][0])

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

main()

Solution (Python):
import math

nm = list(map(int, input().split()))
N, M = nm[0], nm[1]
dp = [1145141919810 for i in range(int(math.pow(2, N)))]
dp[0] = 0
for i in range(M):
    c_num = list(map(int, input().split()))
    cost, NUM = c_num[0], c_num[1]
    index = 0
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        index += int(math.pow(2, tmp[j] - 1))
    for j in range(int(math.pow(2, N))):
        dp[j | index] = min(dp[j | index], dp[j] + cost)
if dp[len(dp) - 1] == 1145141919810:
    print(-1)
else:
    print(dp[len(dp) - 1])

Solution (Python):
import sys
input=sys.stdin.readline
inf=10**9
 
n,m=map(int, input().split())
 
dp=[[inf for _ in range(2**n)] for _ in range(m+1)]
dp[0][0]=0
 
for i in range(1, m+1):
    a,b=map(int, input().split())
 
    state=0
    c=list(map(int, input().split()))
    for x in c:
        state+=(1<<(x-1))
    
    for j in range(2**n):
        dp[i][j]=min(dp[i][j], dp[i-1][j])
        dp[i][j|state]=min(dp[i][j|state], dp[i-1][j|state], dp[i-1][j]+a)
 
if dp[m][2**n-1] == inf:
    print(-1)
    exit()
print(dp[m][2**n-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(len(keys)):
  for j in range(len(dp)-1,-1,-1):
    if dp[j]!=INF:
      if dp[j|keys[i]]>dp[j]+cost[i]:
        dp[j|keys[i]]=dp[j]+cost[i]

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    KV=[None]*m
    for i in range(m):
        K=0
        a,b=map(int,input().split())
        for c in map(int,input().split()):
            c-=1
            K|=1<<c
        KV[i]=(K,a)

    N=1<<n
    dp=[INF]*N
    dp[0]=0
    for K,v in KV:
        ndp=dp[:]
        for i in range(N):
            ndp[i|K]=min(ndp[i|K],dp[i]+v)
        dp=ndp

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