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())
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)

Solution (Python):
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = 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)

Solution (Python):
from itertools import product
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = 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(range(n_bit), 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)

Solution (Python):
from itertools import product
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = 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(range(n_bit), zip(can_open, cost)):
    m = j | x
    dp[m] = min(dp[m], dp[j]+y)

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

Solution (Python):
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for i in range(m):
    for j in range(n_bit):
        dp[j | can_open[i]] = min(dp[j | can_open[i]], dp[j]+cost[i])

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

Solution (Python):
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j in range(n_bit):
    for i in range(m):
        dp[j | can_open[i]] = min(dp[j | can_open[i]], dp[j]+cost[i])

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

Solution (Python):
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

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

for j in range(n_bit):
    for i in range(m):
        dp[j][i+1] = min(dp[j][i+1], dp[j][i])
        dp[j | can_open[i]][i +
                            1] = min(dp[j | can_open[i]][i+1], dp[j][i+1]+cost[i])

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

Solution (Python):
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

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


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

        if (j | can_open[i]) <= n_bit:
            dp[i+1][j | can_open[i]
                    ] = min(dp[i+1][j | can_open[i]], dp[i+1][j]+cost[i])

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

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
l=[]
for i in range(m):
  l2=[]
  a,b=map(int,input().split())
  l2.append(a)
  x=list(map(int,input().split()))
  ct=0
  for i in range(n):
    if i+1 in x:
      ct+=2**i
  l2.append(ct)
  l.append(l2)

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

if dp[m][2**n-1]<10**11:
  print(dp[m][2**n-1])
else:
  print(-1)

Solution (Python):
def main():
    import numpy as np

    n, m = 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 = 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)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    DP = [10**9] * 2**n
    DP[0] = 0
    updated_patterns = {0}
    for _ in range(m):
        cost, types = 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)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    all_patterns = 2**n
    DP = [10**9] * all_patterns
    DP[0] = 0
    for _ in range(m):
        cost, types = map(int, input().split())
        to_open = list(map(int, input().split()))

        openable = 0
        for open in to_open:
            openable += 1 << (open-1)

        for opened in range(all_patterns):
            pattern = opened | openable
            new_cost = DP[opened] + cost
            if DP[pattern] > new_cost:
                DP[pattern] = new_cost

    full_open = 2**n - 1
    ans = DP[full_open]
    if ans == 10 ** 9:
        ans = -1
        
    print(ans)


if __name__ == '__main__':
    main()

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

DP = [10**9] * (2**n)
DP[0] = 0
for _ in range(m):
    cost, types = map(int, input().split())
    to_open = list(map(int, input().split()))

    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)

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 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)

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

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

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

def conv_to_bit(clist):
  ret=0
  for c in clist:
    ret+=2**(c-1)
  return ret

alist=[]
cmat=[]
for i in range(M):
  a,b=map(int,input().split())
  alist.append(a)
  clist=list(map(int,input().split()))
  cmat.append(clist)
  
dp=[]
for i in range(M+1):
  dp.append([float("inf")]*(2**N))
dp[0][0]=0
  
for i in range(M):
  cbit=conv_to_bit(cmat[i])
  for j in range(2**N):
    dp[i+1][j]=dp[i][j]

  for j in range(2**N):
    bit_or=j|cbit
    dp[i+1][bit_or]=min(dp[i+1][bit_or],dp[i][j]+alist[i])
    
if dp[-1][-1]==float("inf"):
  print(-1)
else:
  print(dp[-1][-1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    

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

    
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i, a in key:
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+a)
    print(dp[-1] if dp[-1] != inf else -1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    

    n,m = map(int, input().split())
    
    key = [inf]*(1<<n)
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        if key[binary] > a:
            key[binary] = a

    
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        if key[i] == inf:
            continue
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+key[i])
    print(dp[-1] if dp[-1] != inf else -1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    

    n,m = map(int, input().split())
    
    key = [inf]*(1<<n)
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        if key[binary] > a:
            key[binary] = a

    
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        if key[i] == inf:
            continue
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+key[i])
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    

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

    
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i, a in key:
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    

    n,m = map(int, input().split())
    
    key = [inf]*(1<<n)
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        key[binary] = min(key[binary], a)

    
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        if key[i] == inf:
            continue
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+key[i])
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

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

if __name__ == "__main__":
    main()

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

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 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 map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return 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)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N, M = map(int, input().split())
INF = 10**12
AB = []
C = []
for i in range(M):
    AB.append(tuple(int(x) for x in input().split()))
    C.append(sum(1<<(int(x)-1) for x in input().split()))

dp = [INF]*(1<<N)
dp[0] = 0
for i in range(1<<N):
    for (a, b), c in zip(AB, C):
        m = i | c
        dp[m] = min(dp[m], dp[i]+a)
        
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
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())))
dp = [[10**18] * (2 ** n) for i in range(m+1)]
dp[0][0] = 0
for i,((a,b),c) in enumerate(zip(ab,c)):
  d = 0
  for x in c:
    d += 2 ** (x-1)
  for j in range(2**n):
    NEXT = j | d
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][NEXT] = min(dp[i+1][NEXT], dp[i][j]+a)
ans = dp[m][2**n-1]
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)

Solution (Python):
N, M = map(int, input().split())
a,c = [], []
for _ in range(M):
	ta, _ = map(int, input().split())
	tc = 0
	tmp = list(map(int, input().split()))
	for t in tmp:
		tc += 1 << (t-1)

	a.append(ta)
	c.append(tc)

inf = float('inf')

DP = [[inf] * (1 << N) for _ in range(M)]
for i in range(M):
	DP[i][0] = 0
DP[0][c[0]] = a[0]

for i in range(1, M):
	for s in range(1 << N):
		DP[i][s] = min(DP[i][s], DP[i-1][s])
		DP[i][s | c[i]] = min(DP[i][s|c[i]], DP[i-1][s|c[i]], DP[i-1][s]+a[i])

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

Solution (Python):
n,m=map(int,input().split())
a,c=[],[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  bit=0
  for i in input().split():
    bit|=(1<<(int(i)-1))
  c.append(bit)
inf=float("inf")
dp=[[inf]*(1<<n) 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])
    next_bit=j|c[i]
    dp[i+1][next_bit]=min(dp[i+1][next_bit],dp[i][j]+a[i])
print(dp[-1][-1] if dp[-1][-1]!=inf else -1)

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

Solution (Python):
import sys

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


def resolve():
    n, m = map(int, input().split())
    ABC = []
    for _ in range(m):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        bit = ["0"] * n
        for c in C:
            bit[c - 1] = "1"

        bit = "".join(bit)
        ABC.append([a, b, int(bit, 2)])

    dp = [f_inf for _ in range(1 << n)]
    dp[0] = 0
    for i in range(1 << n):
        for a, b, c in ABC:
            idx = i | c
            dp[idx] = min(dp[idx], dp[i] + a)

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

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


def resolve():
    n, m = map(int, input().split())
    ABC = []
    for _ in range(m):
        a, b = 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])


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
graph = [None] * m
for i in range(m):
  a, b = map(int, sys.stdin.readline().split())
  res = 0
  for c in map(int, sys.stdin.readline().split()):
    res |= 1 << (c - 1)
    graph[i] = (a, res)


def main():
  dp = [[0] * (1 << n) for _ in range(m + 1)]
  for i in range(1, 1 << n):
    dp[0][i] = inf

  for i in range(m):
    for j in range(1 << n):
      dp[i+1][j] = min(dp[i][j ^ (j & graph[i][1])] + graph[i][0], dp[i][j])

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

if __name__ == '__main__':
  main()

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

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

ab = []
c = []
for _ in range(m):
    ab_i = tuple(map(int,input().split()))
    ab.append(ab_i)
    c_i = tuple(map(int,input().split()))
    c_i_bit = 0
    for j in c_i:
        c_i_bit += 1 << (j-1)
    c.append(c_i_bit)

inf = 10**10
dp = [ [inf] * 2**n for _ 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+1][j], dp[i][j])
        dp[i+1][j|c[i]] = min(dp[i+1][j|c[i]], dp[i][j] + ab[i][0])

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

Solution (Python):


import sys


















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, m = mi()
    
    k = [None]
    for _ in range(m):
        a, _ = mi()
        k.append([a, lmi()])

    d = 2 ** n
    dp = [[0] * d for _ in range(m + 1)]
    for j in range(1, d):
        dp[0][j] = inf
    for j in range(1, d):
        for i in range(1, m + 1):
            cost = k[i][0]
            able_to_open = k[i][1]
            mask = 0b0
            for num in able_to_open:
                mask |= (1 << (num - 1))
            
            mask = ~mask
            
            j_prime = j & mask
            dp[i][j] = min(dp[i-1][j], dp[i-1][j_prime] + cost)
    
    print(dp[m][d-1]) if dp[m][d-1] != inf else print(-1)

if __name__ == "__main__":
    main()

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

Solution (Python):
N, M = map(int, input().split())
inf = int(1e10)
dp = [inf] * (1 << N) 


dp[0] = 0
bits = set()
bits.add(0)

for i in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    
    key = 0
    for t in c:
        key += 1 << (t - 1)
    
    
    add_bits = set()
    for bit in bits:
        tmp = bit | key
        if dp[bit] + a < dp[tmp]:
            dp[tmp] = dp[bit] + a
            add_bits.add(tmp)
    bits |= add_bits
    
if dp[(1 << N) - 1] == inf:
    print(-1)
else:
    print(dp[(1 << N) - 1])

Solution (Python):
N,M=map(int,input().split())
dp=[float("inf") for _ in range(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 v in range(2**N):
        nv=v|c
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Solution (Python):

"""
E - Get Everything
https://atcoder.jp/contests/abc142/tasks/abc142_e

"""
import sys


def solve(N, M):
    dp = [float('inf')] * 2**N
    dp[0] = 0
    for y in range(1, M+1):
        a, b = 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 = map(int, input().split())
    ans = solve(N, M)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

Solution (Python):


N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

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

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        cur = dp[i][state]
        if dp[i+1][used] > cur + A[i]:
            dp[i+1][used] = dp[i][state] + A[i]

        if dp[i+1][state] > cur:
            dp[i+1][state] = cur

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

Solution (Python):
N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    C = list(map(int, input().split()))
    for c in C:
        c -= 1
        s |= 1 << c
    key.append((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)
ans = dp[-1]
if ans != float('inf'):
    print(ans)
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())
    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])

if __name__ == '__main__':
    main()

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

if __name__ == "__main__":
    main()

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
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 debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(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()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def digit(n, m):
    n = str(n)
    while m - len(n):
        n = '0' + n
    return n

n, m = MAP()
dp = [[inf for _ in range(2 ** n)] for _ in range(m)]
for i in range(m):
    dp[i][0] = 0
for i in range(m):
    a, b = MAP()
    c = LIST()
    arr = [1 if i + 1 in c else 0 for i in range(n)]
    cnum = 0
    for j in range(n):
        cnum += arr[j] * (2 ** (n - j - 1))
    if i == 0:
        for j in range(1, 2 ** n):
            if (cnum ^ j) & j != 0:
                continue
            dp[i][j] = a
    else:
        for j in range(1, 2 ** n):
            former = (cnum & j) ^ j
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][former] + a)
    debug(dp[i])
if dp[m - 1][2 ** n - 1] >= inf:
    print(-1)
else:
    print(dp[m - 1][2 ** n - 1])