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())
l = []
for i in range(m):
    a,b = map(int,input().split())
    c = 0
    for j in map(int,input().split()):
        c += (1<<(j-1))
    l.append((c,a))
dp = {0:0}
for i in l:
    items = list(dp.items())
    for j in items:
        ij = (i[0] | j[0], i[1] + j[1])
        if not dp.get(ij[0]):
            dp[ij[0]] = ij[1]
        else:
            if dp[ij[0]] > ij[1]:
                dp[ij[0]] = ij[1]

print(dp.get(2**n-1,-1))

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

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


def main():
    N, M = map(int, input().split())
    keys = []
    for _ in range(M):
        a, _ = map(int, input().split())
        c = 0
        for i in list(map(int, input().split())):
            c += (1 << (i-1))
        keys.append((a, c))

    inf = float("inf")
    dp = [[inf]*(1 << N) for _ in range(M+1)]
    dp[0][0] = 0

    for i, (a, c) in enumerate(keys):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][j | c] = min(dp[i+1][j | c], dp[i][j] + a)

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


if __name__ == '__main__':
    main()

Solution (Python):


def main():
  n, m = map(int, input().split())
  p = 2 ** n
  inf = 10 ** 9
  dp = [inf] * p
  dp[0] = 0

  for _ in range(m):
    a, _ = 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])

if __name__ == '__main__':
    main()

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    dp = [10 ** 15] * (2 ** n)
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        c = sum([2 ** (i - 1) for i in list(map(int, input().rstrip('\n').split()))])
        for j in range(len(dp)):
            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
input = sys.stdin.readline

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

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

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

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

Solution (Python):
n,m = map(int,input().split())
 
dic = {0:0}
 
for i in range(m):
  a,b = map(int,input().split())
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    if (k|c) in dic2.keys():
      dic2[k|c] = min(dic2[k|c],a+v)
    else:
      dic2[k|c] = a+v
 
  dic = dic2
 
if ((2**n)-1) in dic.keys():
  print(dic[(2**n) -1])
else:
  print(-1)

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

a_list = []
c_list = []

for i in range(M):
    a,b = list(map(int,input().split()))
    a_list.append(a)
    c = list(map(int,input().split()))
    d = 0
    for cc in c:
        d += 2**(cc-1)
    c_list.append(d)

DP = [[10**27]*(2**N) for i in range(M+1)]
DP[0][0]=0
for i in range(1,M+1):
    for j in range(2**N):
        
        DP[i][j] = min(DP[i][j],DP[i-1][j])
        DP[i][c_list[i-1] | j] = min(DP[i][c_list[i-1] | j],DP[i-1][j] + a_list[i-1])


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

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

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

f=[10**7 for x in range(2**n)]
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)
  f[s]=min(f[s],a)

l=[]
for i in range(2**n):
  if f[i] != 10**7:
    l.append([i,f[i]])

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)

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

l = []

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    bit_c = 0
    for x in c:
        bit_c = bit_c | (1<<(x-1))
    l.append([a,bit_c])

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

dp[1][0] = 0
dp[1][l[0][1]] = l[0][0]

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

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

Solution (Python):
import sys


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


if __name__ == '__main__':
    solve()

Solution (Python):
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 j in range(b):
        s |= 1<<(c[j]-1)
    key.append([s, a])

INF = 10**8
dp = [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)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Solution (Python):

from functools import reduce


def solve(*args: str) -> str:
    a_max = 1+12*10**5
    n, m = map(int, args[0].split())
    cache = {}

    for i in range(1, 1+2*m, 2):
        a, _ = map(int, args[i].split())
        c = reduce(
            lambda x, y: x | 1 << y-1,
            [0] + list(map(int, args[i+1].split()))
        )
        cache[c] = min(cache.get(c, a_max), a)

    for C in tuple(cache.items()):
        unlocked, cost = C
        for E in tuple(cache.items()):
            c, a = E
            cache[unlocked | c] = min(
                cache.get(unlocked | c, a_max),
                a + cost
            )

    return str(cache.get(2**n-1, -1))


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

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

for _ in range(M):
    cost, _ = map(int, input().split())
    mask = 0
    for i in map(int, input().split()):
        mask |= (1 << (i - 1))
    keys.append((cost, mask))

dp = [[float('inf')] * (1 << N) for _ in range(M + 1)]
dp[0][0] = 0

for i, (cost, mask) in enumerate(keys, start=1):
    for state in range(1 << N):
        dp[i][state] = min(dp[i - 1][state], dp[i][state])
        dp[i][state | mask] = min(dp[i - 1][state] + cost, dp[i][state | mask])

ans = dp[M][(1 << N) - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

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

  
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N,M = map(int, input().split())
    inf = 10**9
    p = 2**N
    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])
 
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 ** (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])

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

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

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    pw = 2 ** n
    dp = [10 ** 20] * pw
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        c = sum(2 ** (i - 1) for i in list(map(int, input().rstrip('\n').split())))
        for j in range(pw):
            if dp[j | c] > dp[j] + a:
                dp[j | c] = dp[j] + a
    if dp[-1] == 10 ** 20:
        print(-1)
    else:
        print(dp[-1])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    tc = list(map(int, input().split()))
    c.append(tc)
p = 2**n
dp = [float('inf')] * p
dp[0] = 0

for i in range(m):
    for j in range(p):
        t = p-1
        for cc in c[i]:
            t -= (1 << (cc-1))
        for cc in c[i]:
            if j >> (cc-1) & 1:
                dp[j] = min(dp[j], dp[j&t] + a[i])
if dp[p-1] == float('inf'):
    print(-1)
else:
    print(dp[p-1])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
a = [0]*M; b = [0]*M; c = [0]*(M)
for i in range(M):
    a[i], b[i] = LI()
    C = LI()
    for j in range(b[i]):
        c[i] += 2**(C[j]-1)
cou = int(0)

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

for i in range(2**N):
    for k in range(M):
        if i^c[k]!=i-c[k]:
            dp[i|c[k]] = min(dp[i|c[k]],dp[i]+a[k])

ans = dp[2**N-1]
if ans==inf:
    ans = -1
print(ans)

Solution (Python):
N, M = map(int, input().split())
INF = 10**9
dic = [0]*(M+1)
bit = 0
for i in range(M):
  a, b = map(int, input().split())
  c = [int(x) for x in input().split()]
  j = 0
  s = 0
  for n in range(N):
    if n==c[j]-1:
      s += 2**n
      j += 1 if j<len(c)-1 else 0
    else:
      s += 0
  bit |= s
  dic[i+1] = (a,s)
if bit!=(1<<N)-1:
  print(-1)
else:
  dp = [INF]*(1<<N)
  dp[0] = 0
  for i in range(1,M+1):
    a, s = dic[i]
    for j in range(1<<N):
      dp[j|s] = min(dp[j]+a, dp[j|s])
  print(dp[-1])

Solution (Python):
def p_e():
    N, M = map(int, input().split())
    max_value = (10 ** 5) * 12 + 1
    dp_len = 2 ** N
    dp = [max_value] * dp_len
    dp[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        keys = list(map(int, input().split()))
        index = 0
        for key in keys:
            index += 2 ** (key - 1)

        for i in range(dp_len):
            if dp[i] == max_value:
                continue
            dp_index = i | index
            dp[dp_index] = min(dp[dp_index], dp[i] + a)

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


if __name__ == '__main__':
    p_e()

Solution (Python):




from itertools import *
import sys










def read_input():
	[N, M] = map(int, raw_input().split())
	v = []
	for k in range(M):
		a, b = map(int, raw_input().split())
		cs = [ int(e) for e in raw_input().split() ]
		flag = reduce(lambda x, y: x | (1 << (y-1)), cs, 0)
		v.append((a, flag))
	return (N, v)

def proc():
	N, v = read_input()
	
	L = 1 << N
	memo = [10**9] * L
	memo[0] = 0
	for n in range(L-1):
		for a, flag in v:
			n1 = n|flag
			memo[n1] = min(memo[n1], memo[n] + a)
	
	if memo[L-1] == 10**9:
		return -1
	else:
		return memo[L-1]




print proc()

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

DP = [[10**9]*(2**N) for i in range(M+1)]
DP[0][0] = 0
key = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    d = 0
    for j in c:
        d += 2**(j-1)
    key.append([a,d])
for i in range(M):
    cost,p = key[i]
    for j in range(2**N):
        q = j - (p&j)
        DP[i+1][j] = min(DP[i][j],cost+DP[i][q])
ans = DP[-1][-1]
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    INF = float('inf')
    
    L = 2 ** N
    dp = [INF] * L
    dp_next = [INF] * L
    
    nums = [2 ** i for i in range(N)]
    
    for i in range(M):
        a, b = map(int, input().split())
        b = sum([nums[c-1] for c in list(map(int, input().split()))])            
    
        dp[b] = min(dp[b], a)
        for j in range(L):
            n = j | b
            dp_next[n] = min(dp[n], dp_next[n], dp[j]+a)
        
        for j in range(L):
            dp[j] = dp_next[j]
            
    if dp[-1] == INF: print(-1)
    else: print(dp[-1])

if __name__ == '__main__':
    main()

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

dp = [-1] * (2**n)
dp[0] = 0

def to_bits(xs):
    bits = 0
    for x in xs:
        bits += 2**(x-1)
    return bits

costs = []
bits = []
for i in range(m):
    c,k = words(int)
    costs.append(c)
    ys = words(int)
    bits.append(to_bits(ys))




for cur in range(2**n):
    if dp[cur] == -1:
        continue
    
    for c,b in zip(costs, bits):
        next = cur | b
        if dp[next] == -1 or dp[next] > dp[cur] + c:
            dp[next] = dp[cur] + c

print(dp[2**n-1])

Solution (Python):
def main():
    N,M = map(int, input().split())
    inf = 10**9
    p = 2**N
    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])

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N,M = map(int, input().split())
    inf = 10**9
    p = 2**N
    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])

if __name__ == "__main__":
    main()

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

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

def binize(vn):
    res = 0
    for n in vn:
        res |= 1 << (n-1)
    return res


N, M = map(int, input().split())
mK = []
for i in range(M):
    a, b = map(int, input().split())
    vc = list(map(int, input().split()))
    mK.append((a, binize(vc)))


allOpen = 2**N - 1
INF = float("inf")


dp = []
dp.append([0,]+[INF,]*allOpen)


for na,n in mK:
	nDP = dp[-1]
	for c,pa in enumerate(dp[-1]):
		nDP[n|c] = min(nDP[n|c], pa+na)
	dp.append(nDP)

res = dp[-1][-1]

print(res if res != INF else -1)

Solution (Python):
n, m = map(int, input().split())
inf = 1e9
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]))

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

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


def main():
	N, M = MAP()
	dp = [INF]*(1<<N)
	dp[0] = 0

	for _ 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, 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
from bisect import bisect

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()
dp = [INF]*(1<<N)
dp[0] = 0

for _ 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])

Solution (Python):
MAX_INT = int(10e10)

N, M = list(map(int,input().split()))
Val = [0 for _ in range(M)]
Key = [0 for _ in range(M)]
for i in range(M):
  v, b = list(map(int,input().split()))
  k =  list(map(int,input().split()))
  Val[i] = v
  tmp = 0
  for num in k:
    tmp += 2**(num-1)
  Key[i] = tmp



dp = [MAX_INT for _ in range(1<<N)]
dp[0] = 0
for i in range(1<<N):
  for x in range(M):
    
    dp[i|Key[x]] = min(dp[i|Key[x]], dp[i] + Val[x])

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

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

Solution (Python):
n, m = map(int, input().split())
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 = set(map(int, input().split()))
  c = 0
  for l in k:
    c += 2**(l-1)
  for j in range(2**n):
    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])

Solution (Python):
n, m = list(map(lambda x:int(x), input().split()))
 
key_list = {}
 
for i in range(m):
    key_price, _ = list(map(lambda x:int(x), input().split()))
    open_list = list(map(lambda x:int(x), input().split()))
    key_list[i] = [key_price, open_list]
    
situation_val = 1 << n
 
dp = [[float('INF')] * situation_val for i in range(m+1)]
for i in range(m+1):
    dp[i][0] = 0
 
for i in range(m):
    price = key_list[i][0]
    treasure = key_list[i][1]
    key_val = 0
    for v in treasure:
        key_val += (1 << v-1)
        
    for j in range(situation_val):
        key_used_situation = j | key_val
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][key_used_situation] = min(dp[i+1][key_used_situation], dp[i][j]+price)
        
        
ans = dp[m][situation_val-1]

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

Solution (Python):
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

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

    size = (1 << n)

    dp = [inf] * size
    dp[0] = 0

    for _ in range(m):
        price, _ = map(int, input().split())
        key = sum(1 << ind for ind in (int(x) - 1 for x in input().split()))
        for mask in range(size):
            if dp[mask] == inf:
                continue
            n_mask = (mask | key)
            dp[n_mask] = min(dp[n_mask], dp[mask] + price)

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

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

    size = (1 << n)

    dp = [inf] * size
    dp[0] = 0

    for _ in range(m):
        price, _ = map(int, input().split())
        key = sum(1 << ind for ind in (int(x) - 1 for x in input().split()))
        for mask in range(size):
            dp[mask | key] = min(dp[mask | key], dp[mask] + price)

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


if __name__ == '__main__':
    main()

Solution (Python):
inf = 10 ** 8 + 10

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

keys = set()

for i in range(m):
    price, _ = map(int, input().split())
    key = 0
    for ind in (int(x) - 1 for x in input().split()):
        key += (1 << ind)
    keys.add((price, key))

dp = [inf] * (1 << n)
dp[0] = 0

for price, key in sorted(keys):
    for mask in range(1 << n):
        dp[mask | key] = min(dp[mask | key], dp[mask] + price)

ans = dp[(1 << n) - 1]
print(ans if ans != inf else -1)

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


def main():
    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):
            if dp[i | c] > dp[i] + a:
                dp[i | c] = dp[i] + a

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


if __name__ == '__main__':
    main()

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


def main():
    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)


if __name__ == '__main__':
    main()

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

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

DP=[[float('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] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j-(j&key[i][1])])
if DP[-1][-1]==float('inf'):
    print(-1)
else:
    print(DP[-1][-1])

Solution (Python):
N,M = map(int,input().split())
DP = [[10**9]*(2**N)for i in range(M+1)]
DP[0][0] = 0
key = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    rock = 0
    for j in c:
        rock += 2**(j-1)
    key.append([a,rock])
for i in range(M):
    for j in range(2**N):
        DP[i+1][j] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j - (j&key[i][1])])
ans = DP[-1][-1]
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
N, M = map(int, input().split())
a = [0] * M 
c = [[]] * M
INF = 100000001
dp = [INF for i in range(2 ** N)]
for i in range(M):
    a[i], _ = map(int, input().split())
    c[i] = list(map(int, input().split()))

b = []
for l in c:
    g = 0
    for n in l:
        g |= 1 << (n - 1)
    b.append(g)
l = 2 ** N
dp[0] = 0
for s in range(l):
    for i in range(M):
        p = s | b[i]
        dp[p] = min(dp[p], dp[s] + a[i])

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

Solution (Python):
def main():
  Inf = 10**8
  N, M = list(map(int, input().split(" ")))
  keys = []
  for _ in range(M):
      c = list(map(int, input().split(" ")))
      j = list(map(int, input().split(" ")))
      keys.append([c[0], sum([1 << k-1 for k in j])])
  dp = [Inf for _ in range(1 << N)]
  dp[0] = 0
  for i in range(len(dp)):
      for key in keys:
          t = i | key[1]
          dp[t] = min(dp[t], key[0] + dp[i])
  if dp[-1]==Inf:
      print(-1)
  else:
      print(dp[-1])
main()

Solution (Python):

import sys

INF = 1<<32
    
def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[INF] * ((1<<N)+1) for i 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 | c[i]] = min(dp[i+1][j | c[i]], dp[i][j]+a[i])

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



def main():
    
    N, M = map(int, input().split())
    a = []
    b = []
    c = []
    for i in range(M):
        ax, bx = map(int, input().split())
        cx = map(int, input().split())
        a.append(ax)
        b.append(bx)
        ct = 0
        for j in cx:
            ct |= (1<<(j-1))
        c.append(ct)
    solve(N, M, a, b, c)

    
    

if __name__ == '__main__':
    main()

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

Solution (Python):

import sys
INF = float("inf")


def main():
    
    N, M = map(int, input().split())
    a, b, c, d = [], [], [], []

    for i in range(M):
        a_, b_ = map(int, input().split())
        c_ = tuple(map(int, input().split()))
        d_ = 0
        for keta in c_:
            d_ |= 1 << keta-1
        a.append(a_)
        b.append(b_)
        c.append(c_)
        d.append(d_)

    DP = [INF]*(2**N)
    DP[0] = 0

    for i in range(M):
        DPnext = DP[:]
        for k in range(2**N):
            DPnext[k | d[i]] = min(DP[k | d[i]], DP[k]+a[i], DPnext[k | d[i]])
        DP = DPnext
    if DP[-1] == INF:
        print(-1)
    else:
        print(DP[-1])
    pass


if __name__ == '__main__':
    main()

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

Solution (Python):
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())
    d = sum((1<<p-1) for p in list(map(int, input().split()))) 
    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])

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