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

AB = []
AB_append = AB.append
C = []
C_append = C.append
for _ in range(M):
    a, b = map(int, input().split())
    AB_append((a, b))
    c = list(map(int, input().split()))
    C_append(c)


ans = [10 ** 18] * (2 ** (N + 1))
ans[0] = 0
for i in range(M):
    tmp = 0
    for j in C[i]:
        tmp += 2 ** (j - 1)
    
    for j in range(2 ** N):
        
        if ans[j] == 10 ** 18:
            pass
        else:
            ans[j | tmp] = min(ans[j | tmp], ans[j] + AB[i][0])

if ans[2 ** N - 1] == 10 ** 18:
    print (-1)
    exit()
print (ans[2 ** N - 1])

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

def main():
    N, M = map(int, input().split())
    INF = int(1E8)
    dp = [INF for _ in range(2**N)]
    A = [None for _ in range(M)]
    for j in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        ind = 0
        for c in C:
            ind += 2**(c-1)
        A[j] = (ind, a)
        dp[ind] = min(dp[ind], a)

    Id = [i for i in range(2**N)]
    Id.sort(key=lambda x: bin(x).count('1'))

    for x in Id:
        for ind, a in A:
            dp[x|ind] = min(dp[x|ind], dp[x]+a)
    if dp[2**N-1] >= INF:
        print(-1)
    else:
        print(dp[2**N-1])

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])

Solution (Python):
from collections import defaultdict
N,M = map(int,input().split(' '))

a = []
b = []
c = []
for i in range(1,M+1):
	a_,b_ = map(int,input().split(' '))
	a.append(a_)
	
	c_ = list(map(int,input().split(' ')))
	op = 0
	for t in c_:
		op += (1 << (t-1))
	c.append(op)

dic = defaultdict(lambda: sum(a)+1)
dic[0] = 0
for i in range(M):
	val = a[i]
	op = c[i]
	keys = list(dic.keys())
	for k in keys:
		dic[k | op] = min(dic[k|op] , dic[k] + val)

if dic[2**N-1] == sum(a)+1:
	print(-1)
else:
	print(dic[2**N-1])

Solution (Python):
import math
from functools import reduce
from collections import deque
from itertools import combinations
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

def subsets(items):
    _subsets_=[]
    for i in range(len(items) + 1):
        for c in combinations(items, i):
            _subsets_.append(c)
    return _subsets_

INF = 999999999999999999999999

n,m = get_nums_l()


keys = [INF] * (2 ** (n+2))

for _ in range(m):
    cost, b = get_nums_l()
    ccc = get_nums_l()

    


    for s in subsets(ccc):
        keyn = 0
        
        for c in s:
            keyn += 2 ** c
        
        
        if keys[keyn] > cost:
            keys[keyn] = cost




for i in range(1,n+1):
    if keys[2**i] == INF:
        print(-1)
        exit()

memo=[None] * (2 ** (n+2))

def solve(targets):

    lent = len(targets)
    
    

    if lent == 0:
        return 0

    if lent == 1:
        memo[2*list(targets)[0]] = keys[2*list(targets)[0]]
        
        return keys[2**list(targets)[0]]

    

    keyn=0
    for c in targets:
        keyn += 2 ** c
    
    if memo[keyn]:
        return memo[keyn]

    _min = keys[keyn]

    for s in subsets(targets):
        if len(s) in (0, lent):
            continue
        rev = targets.difference(s)
        cost = solve(s) + solve(rev)
        if _min > cost:
            _min = cost
    memo[keyn] = _min
    
    return _min


ans = solve(set(range(1, n+1)))

print(ans if ans < INF else -1)

Solution (Python):
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    cost = dict()
    for i in range(2 ** N): cost[i] = -1
    cost[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        c = [int(c) for c in input().split()]
        bit = 0
        for j in c: bit += 2 ** (j - 1)
        for i in range(2 ** N):
            if cost[i] > -1:
                if cost[i | bit] > -1:
                    cost[i | bit] = min(cost[i | bit], cost[i] + a)
                else: cost[i | bit] = cost[i] + a

    

    print(cost[2 ** N - 1])
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
a = []
c = []
dp = defaultdict(lambda: 1000000000)
for i in range(M):
    ai, bi = map(int, input().split())
    a.append(ai)
    c.append(sum([1 << int(ci) - 1 for ci in input().split()]))

dp[0] = 0
for i in range(M):
    for k, v in list(dp.items()):
        dp[k | c[i]] = min(dp[k | c[i]], dp[k] + a[i])
print(dp[(1 << N) - 1] if (1 << N) - 1 in dp else -1)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def main():
    box_num, kagi_num = map(int, input().split())

    kagi_data = defaultdict(lambda: 10 ** 10)
    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        money = a[0]
        ind = 0
        for ele in b:
            ind += 2 ** (ele - 1)
        kagi_data[ind] = min(kagi_data[ind], money)

        for key, value in list(kagi_data.items()):
            kari = ind | key
            kagi_data[kari] = min(money + value, kagi_data[kari])

    ans = kagi_data[2 ** (box_num) - 1]
    if ans == 10 ** 10:
        print(-1)
    else:
        print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
INF = 10**10

N, M = map(int, input().split())
costs = []
keys = []
for _ in range(M):
    A, B = map(int, input().split())
    cs = list(map(int, input().split()))
    costs.append(A)
    
    key = 0
    for c in cs:
        key |= 1<<(c-1)
    keys.append(key)


maskss = [[] for _ in range(N+1)]
num1s = [0] * (2**N)
for S in range(2**N):
    num = bin(S).count('1')
    maskss[num].append(S)
    num1s[S] = num

dpAll = [INF] * (2**N)
for S in range(2**N):
    for cost, key in zip(costs, keys):
        if S & key == S:
            if cost < dpAll[S]:
                dpAll[S] = cost

dp = [INF] * (2**N)
for S in range(2**N):
    cost = dpAll[S]
    num1 = num1s[S]
    for k in range(1, (num1+1)//2+1):
        for mask in maskss[k]:
            if mask & S == mask:
                m2 = S^mask
                c2 = dp[mask] + dp[m2]
                if c2 < cost:
                    cost = c2
    dp[S] = cost

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

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

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def divisor(n): 
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = copy(now_data_kari)

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    check_set = set()
    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = copy(now_data_kari)

        bbb = ['0' for i in range(box_num)]
        flg = 1
        for ele in data[aaa][2]:
            if now_data[ele - 1] == 0:
                now_data[ele - 1] = 1
                flg = 0
            if ele >= ind + 1:
                bbb[ele - 1] = '1'
        if flg:
            continue
        bbb = ''.join(bbb)
        if bbb in check_set:
            continue
        check_set.add(bbb)
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()

    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a[0], a[1], b]


    kagi_data = defaultdict(int)
    for i in range(kagi_num):
        a = data[i]
        aaa = 0
        for ele in a[2]:
            aaa += 2 ** (ele - 1)
        bin_data = bin(aaa)[2:]
        bin_data = bin_data.zfill(box_num)

        if bin_data in kagi_data:
            kagi_data[bin_data] = min(a[0], kagi_data[bin_data])
        else:
            kagi_data[bin_data] = a[0]

        aaaaaa = kagi_data.items()

        for key, value in list(aaaaaa):
            aaa = ['0' for i in range(box_num)]
            for i in range(box_num):
                if key[i] == '1' or bin_data[i] == '1':
                    aaa[i] = '1'
            aaa = ''.join(aaa)
            if aaa in kagi_data:
                kagi_data[aaa] = min(value + a[0], kagi_data[aaa])
            else:
                kagi_data[aaa] = value + a[0]


    
    aaa = ['1' for i in range(box_num)]
    aaa = ''.join(aaa)
    if aaa in kagi_data:
        print(kagi_data[aaa])
    else:
        print(-1)







if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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

    for _ in range(m):
        a, b = map(int, input().split())
        cc = list(map(int, input().split()))
        mask = 0
        for c in cc:
            mask += 1 << (c - 1)
        for i in range((1 << n) - 1, -1, -1):
            if dp[i] == inf: continue
            ni = i | mask
            if not 0 <= ni < (1 << n): continue
            dp[ni] = min(dp[ni], dp[i] + a)

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

main()

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

Solution (Python):
import sys

N,M=map(int, raw_input().split())
dp=[ float("inf") for _ in range(2**N)]
dp[0]=0


for _ in range(M):
	a,b=map(int, raw_input().split())
	C=map(int, sys.stdin.readline().split())

	n=0
	for c in C:
		n+=2**(N-c)

	for k in range(2**N-1):
		dp[n|k]=min(dp[n|k],dp[k]+a)

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

Solution (Python):
n, m = map(int, input().split())
dp = [[int(2e8) for _ in range(2**n)] for _ in range(2)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(m):
    a, _ = map(int, input().split())
    k = sum(map(lambda c: 1 << (c - 1), list(map(int, input().split()))))
    for j in range(2**n):
         dp[(i + 1) % 2][j] = min(dp[(i + 2) % 2][j], dp[i % 2][j])
    for j in range(2**n):
         dp[(i + 1) % 2][j | k] = min(dp[(i + 1) % 2][j | k], dp[i % 2][j] + a)
ans = min(dp[0][-1], dp[1][-1])
if int(1e8) < ans:
    ans = -1
print(ans)

Solution (Python):
N,M = map(int,input().split())
INF = float('inf')
V = [INF] * (1<<N)
V[0] = 0
for i in range(M):
    v,_ = map(int,input().split())
    b = 0
    s = list(map(int,input().split()))
    for a in s:
        b |= (1<<(a-1))
    V[b] = min(V[b], v)

vbs = []
for b,v in enumerate(V):
    if v==INF: continue
    vbs.append((v,b))

for v,b in vbs:
    for c in range(1<<N):
        if V[c] == INF: continue
        V[b|c] = min(V[b|c], V[b]+V[c])

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

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

Solution (Python):
from collections import defaultdict
N,M = map(int,input().split(' '))

a = []
b = []
c = []
for i in range(1,M+1):
	a_,b_ = map(int,input().split(' '))
	a.append(a_)
	
	c_ = list(map(int,input().split(' ')))
	op = 0
	for t in c_:
		op += (1 << (t-1))
	c.append(op)

dic = defaultdict(lambda: sum(a)+1)
dic[0] = 0
for i in range(M):
	val = a[i]
	op = c[i]
	keys = list(dic.keys())
	for k in keys:
		dic[k | op] = min(dic[k|op] , dic[k] + val)

if dic[2**N-1] == sum(a)+1:
	print(-1)
else:
	print(dic[2**N-1])

Solution (Python):
N,M = [int(x) for x in input().split()]
a = []
b = []
c = []
for i in range(M):
  A,B = [int(x) for x in input().split()]
  C = [int(x) for x in input().split()]
  a.append(A)
  b.append(B)
  c.append(C)
c1 = []
for i in range(M):
  l = 0
  for j in c[i]:
  	l = l|1<<(j-1)
  c1.append(l)
cnt = [0]*(1<<N)
dp = [[float('inf')]*(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][j],dp[i+1][j])
    dp[i+1][j|c1[i]] = min(dp[i][j]+a[i],dp[i+1][j|c1[i]])
if dp[M][-1]!=float("inf"):
  print(dp[M][-1])
else:
  print(-1)
"""
for s in range(1<<N):
    for i in range(N):
        if not s & (1 << i) and s & edges[i] == edges[i]:
            nextS = s| (1 << i)
            disk[nextS] = disk[s] + x[i]
            dp[nextS] = min(dp[nextS], max(dp[s], disk[nextS]))
            disk[nextS] -= cost[i]
print(dp[-1])
"""

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

ret = [float('inf')] * (1 << N)
for _ in range(M) :
    a, b = map(int, input().split())
    c = 0
    for i in input().split() :
        c |= 1 << (int(i) - 1)
    ret[c] = min(ret[c], a)

for i in range(1 << N) :
    if ret[i] == float('inf') :
        continue
    for j in range(1 << N) :
        k = i | j
        ret[k] = min(ret[k], ret[i] + ret[j])

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

Solution (Python):
import sys
from heapq import *

input = sys.stdin.readline

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

error = 10000000000

q = []
minc = [error]*(2**N)
for i in range(M):
	a, b = list(map(int,input().split()))
	c = list(map(int,input().split()))
	c10 = 0
	for ci in c:
		c10 += 2**(ci-1)

	minc[c10] = min(minc[c10],a)

while True:
	tmin = min(minc)
	if tmin==minc[-1]: break
	ti = minc.index(tmin)
	for i, mini in enumerate(minc):
		if mini!=error:
			ni = ti | i
			minc[ni] = min(minc[ni],tmin+mini)
	minc[ti] = error

ans = minc[-1]
if ans==error: ans = -1
print(ans)

Solution (Python):

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

AB = []
AB_append = AB.append
C = []
C_append = C.append
for _ in range(M):
    a, b = map(int, input().split())
    AB_append((a, b))
    c = list(map(int, input().split()))
    C_append(c)


ans = [10 ** 18] * (2 ** (N + 1))
ans[0] = 0
for i in range(M):
    tmp = 0
    for j in C[i]:
        tmp += 2 ** (j - 1)
    
    for j in range(2 ** N):
        
        if ans[j] == 10 ** 18:
            pass
        else:
            ans[j | tmp] = min(ans[j | tmp], ans[j] + AB[i][0])

if ans[2 ** N - 1] == 10 ** 18:
    print (-1)
    exit()
print (ans[2 ** N - 1])

Solution (Python):
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))

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

Solution (Python):
N,M = map(int,input().split())
box = [float('inf')]*(2**N)

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

Solution (Python):
INF = 10**10

N, M = map(int, input().split())
costs = []
keys = []
for _ in range(M):
    A, B = map(int, input().split())
    cs = list(map(int, input().split()))
    costs.append(A)
    
    key = 0
    for c in cs:
        key |= 1<<(c-1)
    keys.append(key)


maskss = [[] for _ in range(N+1)]
num1s = [0] * (2**N)
for S in range(2**N):
    num = bin(S).count('1')
    maskss[num].append(S)
    num1s[S] = num

dpAll = [INF] * (2**N)
for S in range(2**N):
    for cost, key in zip(costs, keys):
        if S & key == S:
            if cost < dpAll[S]:
                dpAll[S] = cost

dp = [INF] * (2**N)
for S in range(2**N):
    cost = dpAll[S]
    num1 = num1s[S]
    for k in range(1, (num1+1)//2+1):
        for mask in maskss[k]:
            if mask & S == mask:
                m2 = S^mask
                c2 = dp[mask] + dp[m2]
                if c2 < cost:
                    cost = c2
    dp[S] = cost

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

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

dp = [float("inf")]*(2**n)

p = []
used = [True]*(2**n)

for _ in range(m):
    a,b = map(int,input().split())
    c = tuple(map(int,input().split()))
    jkl = 0
    for e in c:
        jkl += 1 << (e-1)
    p.append(jkl)
    dp[jkl] = min(dp[jkl],a)
    used[jkl] = False

tank = []

while True:
    tank = []
    for e in p:
        for ep in p:
            if dp[e|ep] > dp[e]+dp[ep]:
                dp[e|ep] = dp[e]+dp[ep]
                if used[e|ep]:
                    tank.append(e|ep)
                    used[e|ep] = False

    if len(tank) == 0:
        break
    for e in tank:
        p.append(e)

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

Solution (Python):
import copy
from collections import defaultdict
N, M = map(int, input().split())
ac = []

dp = defaultdict(lambda: 10 ** 5 + 1)


for _ in range(M):
    
    ac.append([int(input().split()[0]), frozenset(map(int, input().split()))])

ac.sort()
for a, cs in ac:
    if dp[cs] > a:
    
        dp[cs] = a
        dp2 = copy.copy(dp)
        for k, v in dp2.items():
            
            k |= cs
            dp[k] = min(v + a, dp[k])


ans = dp[frozenset(range(1, N + 1))]
if ans == 10 ** 5 + 1:
    ans = -1
print(ans)

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

a = [0] * m
b = [0] * m
c = list()
d = list()

def to_int(c):
    a = [0 , 1, 2, 4, 8, 16 , 32, 64, 128, 256, 512, 1024, 2048]
    result = 0
    for ci in c:
        result += a[ci]
    return result


state = [-1] * 2**n
state[0] = 0

for i in range(m):
    a[i], b[i] = map(int, input().split(" "))
    c.append( list(map(int, input().split(" "))))
    d.append(to_int(c[i]))
    
    for j in range(0,2**n):
        

        if state[j] != -1 and (state[j | d[i]] == -1 or state[j | d[i]] > state[j] + a[i]):
            state[j | d[i]] = state[j] + a[i]
    


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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

N, M = map(int, input().split())
dp = [[INF] * (1<<N) for i in range(M+1)]
dp[0][0] = 0
for i in range(M):
    a, b = map(int, input().split())
    c = [int(x)-1 for x in input().split()]
    mask = 0
    for x in c:
        mask |= 1<<x
    for s in range(1<<N):
        dp[i+1][s] = min(dp[i+1][s], dp[i][s])
        dp[i+1][s|mask] = min(dp[i+1][s|mask], dp[i+1][s]+a)
ans = dp[M][(1<<N)-1] if dp[M][(1<<N)-1] != INF else -1
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]




def change(iter, org):
    return sum([org[i-1] for i in iter])

def main():
    n, m = LI()
    cs = []
    a_s = []
    b_s = []
    org = [2**i for i in range(n)]
    for i in range(m):
        a, b = LI()
        a_s.append(a)
        b_s.append(b)
        cs.append(change(LI(), org))

    mem = [[INF for i in range(2**n)] for i in range(m)]

    mem[0][0] = 0
    mem[0][cs[0]] = a_s[0]

    for i in range(1, m):
        mem[i][0] = 0
        for j in range(2**n):
            mem[i][j] = mem[i-1][j]
        for j in range(2**n):
            if mem[i-1][j] != INF:
                

                mem[i][j | cs[i]] = min(a_s[i] + mem[i-1][j], mem[i][j | cs[i]])
                
        
    
    print(mem[-1][-1] if mem[-1][-1] != INF else "-1")



if __name__ == '__main__':
    main()

Solution (Python):
def getlist():
	return list(map(int, input().split()))
INF = float("inf")


N, M = getlist()
L = [[INF]  * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
	L[i][0] = 0


for i in range(M):
	a, b = getlist()
	c = getlist()
	C = 0
	for j in c:
		C += 2 ** (j - 1)
	for j in range(2 ** N):
		if L[i][j] != INF:
			L[i + 1][j | C] = min(L[i + 1][j | C], L[i][j] + a)
			L[i + 1][j] = min(L[i + 1][j], L[i][j])

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

Solution (Python):
def main():

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

    s = set()
    d = dict()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        v = 0
        for j in range(b):
            s.add(temp[j])
            v |= 1 << temp[j]
        if v in d: d[v] = min(d[v], a)
        else: d[v] = a

    if(len(s) < N): return -1

    M = len(d)
    cur = dict()
    cur[0] = 0
    for g in d:
        temp = cur.copy()
        for v in temp:
            cost = d[g]
            u = v | g
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


if __name__ == '__main__':
    print(main())

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

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

    DP[j|x]=min(DP[j|x],DP[j]+a)

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

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

A,B = np.array(AB,np.int64).T
C = np.array(C,np.int64)

INF = 10**18
dp = np.full(1<<N,INF,np.int64)
dp[0] = 0

for n in range(1<<N):
    target = n|C
    value = A
    I = np.lexsort((value,target))
    target = target[I]
    value = value[I]
    is_first_elem = np.ones(M,np.bool)
    is_first_elem[1:] = ~(target[:-1] == target[1:])
    target = target[is_first_elem]
    value = value[is_first_elem]
    dp[target] = np.minimum(dp[target],dp[n]+value)

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

Solution (Python):
import heapq as hq
inf = 10 ** 18

N, M = map(int, input().split())
n = 1 << N
dis = [inf] * n
que = []
key = []

for _ in range(M):
    a, _ = map(int, input().split())
    c = map(int, input().split())
    k = 0
    for x in c:
        k += 1 << (x-1)
    key.append((k, a))

dis[0] = 0
hq.heappush(que, (0, 0))

while que != []:
    
    
    d, v = hq.heappop(que)
    if d == dis[v]:
        for gain, cost in key:
            if not (gain & v) == gain:
                to = gain | v
                if dis[to] > d + cost:
                    dis[to] = d + cost
                    hq.heappush(que, (dis[to], to))
if dis[n-1] == inf:
    print(-1)
else:
    print(dis[n-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
MOD = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()

a = []
b = []
c = []

for i in range(M):
    ai, bi = LI()
    ci = LI()
    a.append(ai)
    b.append(bi)
    c.append(ci)

dp = [[MOD] * (1 << N)]*(M+1)

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

for i in range(M):
    for j in range(1<<N):
        boxSets = 0
        for cij in c[i]:
            boxSets |= 1 << (cij - 1)
        dp[i][j | boxSets] = min(dp[i][j | boxSets], dp[i][j] + a[i])

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

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

Solution (Python):
import math

n,m = list(map(int, input().split()))
a = []
b = []
c = []
for i in range(m):
    u,v = list(map(int, input().split()))
    a.append(u)
    b.append(v)
    clist = list(map(int, input().split()))
    temp = 0
    for i in range(len(clist)):
        temp += 2**(clist[i]-1)
    c.append(temp)





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

dp[0][c[0]] = a[0]

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






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

Solution (Python):
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))



X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  if X[i]<10**10:
    for j in range(M):
      if i|c[j]<2**N:
        X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

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



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


for i in range(M):
    a, b = map(int, input().split())
    c = [int(i) for i in input().split()]

    bit = 0
    for cb in c:
        bit += 2**(cb-1)

    for fromb in range(2**N):
        dp[fromb | bit] = min(dp[fromb | bit], dp[fromb]+a)

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

Solution (Python):
n,m = map(int,input().split())
dp = [[10**10 for i in range(m+1)] for j in range(1<<n)]

for i in range(m+1):
    dp[(1<<n)-1][i] = 0


for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    S_c = 0
    for x in c:
        S_c += 1<<(x-1)
    
    for s in range(1<<n):
        dp[s][i+1] = min(dp[s][i],a+dp[s | S_c][i],dp[s][i+1])

    

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

Solution (Python):


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0] * M
keys = [0] * M
inf = 10 ** 12
for i in range(M):
    a[i], _ = map(int, input().split())
    c_list = list(map(int, input().split()))
    keys[i] = sum([2 ** j for j in range(N) if j + 1 in c_list])

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



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

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