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

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    key_set = set(map(int, input().split()))
    key_bin = 0
    for c in key_set:
        key_bin += (2**(c-1))
    keys.append([a, key_bin])


N_bin = 2**N

dp = [[float('inf')]*N_bin for _ in range(2)]
dp[0][0] = 0
for key in range(M):  
    key_val, key_set = keys[key]
    for bit in range(N_bin):  
        dp[(key+1) % 2][bit] = min(dp[(key+1) %
                                      2][bit], dp[key % 2][bit])  
        dp[(key+1) % 2][bit | key_set] = min(dp[(key+1) % 2][bit | key_set],
                                             dp[key % 2][bit]+key_val)  
ans = float('inf')
for c in range(2):
    ans = min(ans, dp[c][-1])
if ans == float("inf"):
    ans = -1
print(ans)

Solution (Python):
n, m = map(int, input().split())
ps = [float('inf')] * 2**n
for _ in range(m):
    a, b = map(int, input().split())
    s = sum([2**(i - 1) for i in map(int, input().split())])
    ps[s] = min(ps[s], a)
    for i in range(2**n):
        if i == s:
            ps[i] = min(ps[i], ps[s])
        elif i & s == i:
            ps[i] = min(ps[i], ps[s])
        elif i & s == s:
            ps[s] = min(ps[i], ps[s])
        else:
            ps[i | s] = min(ps[i | s], ps[i] + ps[s])
if ps[2**n - 1] == float('inf'):
    print(-1)
else:
    print(ps[2**n - 1])

Solution (Python):
n, m = [int(i) for i in input().split()]
def get_dp(x):
    return sum([2**i for i in x])
a = []
c = []
d=set()
for j in range(m):
    a2, _ = [int(i) for i in input().split()]
    a.append(a2)
    temp=[int(i)-1 for i in input().split()]
    c.append(get_dp(temp))
    d |= set(temp)

if len(d) != n:
    print(-1)
    exit()


dp = [10**10] * (2 ** n)
dp[0] = 0
for i,m in zip(c,a):
    for j, k in enumerate(dp):
        if k != 10**10:
            l=j|i
            dp[l] = min(dp[l], k + m)
print(dp[-1])

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

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

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

for n,((a,b),c) in itertools.product(range(1<<N),zip(AB,C)):
    m = n|c
    x = dp[n]+a
    if dp[m] > x:
      dp[m] = x
      
answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)

Solution (Python):
def solve_e(n, m, a_list, k_list):
    dp = [[10 ** 9] * (2 ** n) for _ in range(m + 1)]
    dp[0][0] = 0

    
    for i in range(m):
        k = k_list[i]
        for j in range(2 ** n):
            ll = (k ^ j) + ((k + j - (k ^ j)) // 2) - k
            dp[i + 1][j] = min(dp[i][j], dp[i][ll] + a_list[i])

    
    if dp[m][2 ** n - 1] == 10 ** 9:
        return -1
    else:
        return dp[m][2 ** n - 1]


def main():
    n, m = map(int, (input().split()))
    a_list = [0] * m
    k_list = [0] * m
    for i in range(m):
        a, b = map(int, (input().split()))
        a_list[i] = a
        c_list = list(map(int, (input().split())))
        k_list[i] = sum([2 ** (c - 1) for c in c_list])

    res = solve_e(n, m, a_list, k_list)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):


def solve():
    N, M = map(int, input().split())
    max_int = 2**32-1
    dp = [max_int]*2**N
    dp[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        d = sum(2**c for c in map(int, input().split()))>>1
        for j in range(2**N+1):
            if j|d == d:
                dp[j] = min(dp[j],a)
            elif j&d:
                dp[j] = min(dp[j], dp[j-(j&d)]+a)

    res = dp[-1] if dp[-1] < max_int else -1
    return str(res)

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

Solution (Python):
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M = map(int, input().split())
    keys = []

    for _ in range(M):
        a, _ = map(int ,input().split())
        C = list(map(int, input().split()))
        cMask = 0
        for c in C:
            cMask |= (1 << (c - 1))
        keys.append((a, cMask))

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

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

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

sol()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    
    from collections import defaultdict
    import itertools
    import copy
    
    N,M = map(int,input().split())
    dp = [[float("inf")]*(2**N) for i in range(M+1)]
    dp[0][0] = 0
    
    for i in range(1,M+1):
        
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        tmp = 0
        for k in c:
            tmp += 2**(k-1)
        for j in range(2**N):
            now = j | tmp
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            dp[i][now] = min(dp[i][now],dp[i-1][now], dp[i-1][j]+a)
            
    
    if dp[M][2**N-1] == float("inf"):
        print(-1)
    else:
        print(dp[M][2**N-1])
            
    
    
main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A, B, C):
    d = defaultdict(lambda : sys.maxsize)
    
    def f(t, v):
        if v >= d[t]:
            return sys.maxsize
        else:
            d[t] = v
        n = None
        for i in range(N):
            if  (1 << i) & t == 0:
                n = i + 1
                break
        else:
            return v

        ret = sys.maxsize
        for i, c in enumerate(C):
            if n in c:
                t_  = t
                for j in c:
                    t_ |= 1 << (j-1)
                ret = min(ret, f(t_, v + A[i]))
        return ret
    ans = f(0, 0)
    return  ans if ans != sys.maxsize else -1


def main():
    N, M = read_int_n()
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = read_int_n()
        A.append(a)
        B.append(b)
        C.append(set(read_int_n()))

    print(slv(N, M, A, B, C))

    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    N, M = map(int, input().split())
    
    N2 = 2**N
    X = [10**8+1]*N2
    X[0] = 0

    for i in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))

        k = sum(1<<(c-1) for c in C)
        
        for j in range(N2):
            if X[j|k] > X[j] + a:
                X[j|k] = X[j] + a

    
    ans = X[-1]
    if ans >= 10**8+1:
        ans = -1

    print(ans)
    

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new

ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)

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


n, m = [ int(v) for v in input().split() ]
n_q = 2**n

dp_list = [0] + [ 10**7 for i in range(n_q-1) ]
for i in range(m):
    a, b = [ int(v) for v in input().split() ]
    c_list = [ int(v)-1 for v in input().split() ]
    d = 0
    for j in c_list:
        d += 2**j
    for k in range(n_q):
        if 0 <= k | d < n_q:
            e = k | d
            if dp_list[e] > dp_list[k] + a:
                dp_list[e] = dp_list[k] + a

ans = dp_list[-1]
if dp_list[-1] == 10**7:
    ans = -1
print(ans)

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

for i in range(M):
  t = list(map(int, input().split()))
  k = list(map(int, input().split()))
  x = 0
  for j in k:
    x += (1 << (j - 1))
  abc.append(t + [x])

def nasu(n):
  ans = inf
  for i in range(1, n - 1):
    if ~n & i == 0:
      ans = min(ans, L[i] + L[n ^ i])
  return ans

inf = 10 ** 10
L = [inf] * (1 << N)

for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    for j in range(M):
      if ~abc[j][2] & n == 0:
        L[n] = min(L[n], abc[j][0])
    L[n] = min(L[n], nasu(n))
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

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

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

for m in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    c = [2 ** (ci - 1) for ci in c]
    Keys.append([a, sum(c)])
    keys_set |= set(c)



if len(keys_set) != N:
    print(-1)
    exit()


dp = [[float('inf')] * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i, (a, c) in enumerate(Keys):
    for bs in range(2 ** N):
        dp[i + 1][bs] = min(dp[i + 1][bs], dp[i][bs])
        dp[i + 1][bs | c] = min(dp[i][bs | c], dp[i + 1][bs | c], dp[i][bs] + a)

ans = float('inf')
for d in dp:
    ans = min(ans, d[-1])
print(ans)

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

N,M = map(int,input().split())
AB = [0]*M
C = [0]*M
for i in range(M):
    AB[i] = list(map(int,input().split()))
    C[i] = list(map(int,input().split()))

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

for i,ab in enumerate(AB):
    a,b = ab
    c = sum(1<<(d-1) for d in C[i])
    for t in range(2**N):
        dp[i+1][t] = min(dp[i+1][t],dp[i][t])
        dp[i+1][t|c] = min(dp[i+1][t|c],dp[i][t|c],dp[i][t]+a)
ans = dp[-1][-1]
if ans == INF : ans = -1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
INF=10**9
dp=[INF]*(2**n)
dp[0]=0
cost=[INF]*(2**n)
for i in range(m):
    a,b=map(int,input().split())
    c_list=list(map(int,input().split()))
    c=0
    for j in c_list:
        c+=2**(j-1)
    cost[c]=min(cost[c],a)
import itertools
ns=list(range(n))
for i in range(n):
    com=list(itertools.combinations(ns,i))
    for j in com:
        c=0
        for k in j:
            c+=2**k
        if not dp[c]==INF:
            for k in range(2**n):
                if not cost[k]==INF:
                    dp[c|k]=min(dp[c|k],dp[c]+cost[k])
if dp[2**n-1]==INF:
    print(-1)
else:
    print(dp[2**n-1])

Solution (Python):

import sys
sys.setrecursionlimit(300000)
from itertools import permutations

def solve(N, M, a, b, c):
    MAX = 2 ** N - 1
    INF = float('inf')
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for i in range(M):
        bits = 0
        for j in c[i]:
            bits += (1 << (j - 1))
        for b in range(2 ** N):
            dp[b | bits] = min(dp[b | bits], dp[b] + a[i])
    if dp[MAX] < INF:
        print(dp[MAX])
    else:
        print(-1)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = []
    b = []
    c = []
    for i in range(M):
        A = int(next(tokens))  
        B = int(next(tokens))  
        a.append(A)
        b.append(B)
        c.append([ int(next(tokens)) for _ in range(B) ])
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

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

    input = sys.stdin.readline

    inf = float('inf')

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

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

    for i in range(m):
        cost, _ = map(int, input().split())
        c = tuple(int(x) - 1 for x in input().rstrip().split())

        for mask in range((1 << n) - 1):
            if dp[mask] != inf:
                n_bit = mask
                for cc in c:
                    n_bit |= (1 << cc)
                dp[n_bit] = min(dp[n_bit], dp[mask] + cost)
                

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


if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
tr = [ 10 ** 18 for _ in range(2**n) ]
tr[0] = 0
key = []
for _ in range(m):
  cost,b = map(int,input().split())
  raw = list(map(int,input().split()))
  get = 0
  for i in range(b):
    get += 2 ** (raw[i]-1)
  key.append([get,cost])

key.sort()

for j in range(2**n):
  for k in range(m):
    get,cost = key[k]
    tr[get | j] = min(tr[get | j],cost+tr[j])
    
    
  
if tr[2**n-1] == 10 ** 18:
  print(-1)
else:
  print(tr[2**n-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
cost = [0 for _ in range(m)]
key_set = [0 for _ in range(m)]
for i in range(m):
    a, b = LI()
    cost[i] = a
    trs = LI()
    ret = 0
    for j in trs:
        ret += 1 << (j - 1)
    key_set[i] = ret





dp = [INF] * (2 ** n)
dp[0] = 0
for j in range(m):
    for k in range(2 ** n):
        dp[key_set[j] | k] = min(dp[k] + cost[j], dp[key_set[j] | k])



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

Solution (Python):
n,m = map(int,input().split())
inf = 1000000000
a = []
b = []
c = []
for i in range(m):
    aa,ba = map(int,input().split())
    ca = list(map(int,input().split()))
    k = 0
    for i in range(ba):
        k = k | (1 << ca[i]-1)
    a.append(aa)
    b.append(ba)
    c.append(k)

p = 2**n

dp = [[inf for i in range(p)] for i in range(m)]

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



for i in range(1,m):
    for j in range(p):
        ind = j | c[i]
        dp[i][ind] = min ( min(dp [i-1][j] + a[i], dp[i][ind]), dp[i-1][ind])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

ans = dp[m-1][p-1]

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    keys=[0]*m
    cost=[0]*m
    for i in range(m):
        a,b=map(int,input().split())
        cost[i]=a
        key=0
        for c in map(int,input().split()):
            key+=(1<<c-1)
        keys[i]=key
    N=2**n
    dp=[INF]*N
    dp[0]=0
    for k in range(N):
        for i in range(m):
            dp[k|keys[i]]=min(dp[k|keys[i]],dp[k]+cost[i])
    print(dp[N-1] if dp[N-1]!=INF else -1)
resolve()

Solution (Python):
def to_bit(n):
	ret = [0 for i in range(12)]
	i = 0
	while n > 1:
		ret[i] = n % 2
		n = n // 2
	return ret

def to_int(B):
	return sum([B[i] * 2**i for i in range(12)])

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 x in range(12)]
	for x in c:
		C[x-1] = 1
	key.append((a, to_int(C)))
dp = [[-1 if j > 0 else 0 for j in range(2**N)] for i in range(M)]
dp[0][key[0][1]] = key[0][0]
for i in range(M-1):
	cost = key[i+1][0]
	bit = key[i+1][1]
	for j in range(2**N):
		if dp[i][j] >= 0:
			if dp[i+1][j] == -1:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = min(dp[i+1][j], dp[i][j])
			I = i+1
			J = j | bit
			if dp[I][J] == -1:
				dp[I][J] = dp[i][j] + cost
			else:
				dp[I][J] = min(dp[I][J], dp[i][j] + cost)
print(dp[M-1][2**N-1])

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

key_prices = []
keys = []

for i in range(M):
	a, b = list(map(int, input().strip().split()))
	key_prices.append(a)
	bits = 0
	for c in input().strip().split():
		c = int(c) - 1
		bits += (2 ** c)
	keys.append(bits)

count = (2 ** N)
min_prices = [None] * count
min_prices[0] = 0

for price, key in zip(key_prices, keys):
	for bits in range(count):
		base_price = min_prices[bits]
		if base_price != None:
			new_bits = bits | key
			new_price = base_price + price
			old_price = min_prices[new_bits]
			if old_price == None or old_price > new_price:
				min_prices[new_bits] = new_price

min_price = min_prices[count - 1]
if min_price != None:
	print(min_price)
else:
	print("-1")

Solution (Python):

import sys
input=sys.stdin.readline

def main():
    n,m=map(int,input().split())
    Cost=[0]*m
    Key=[0]*m
    for i in range(m):
        a,b=map(int,input().split())
        C=tuple(map(int,input().split()))
        Cost[i]=a
        for c in C:
            Key[i]+=1<<(c-1)
    
    DP=[[float('inf')]*(1<<n) for _ in range(m+1)]
    for i,(c,k) in enumerate(zip(Cost,Key)):
        DP[i+1][k]=min(DP[i][k],c)
        for j in range(1,1<<n):
            DP[i+1][j]=min(DP[i][j],DP[i+1][j])
            DP[i+1][j|k]=min(DP[i+1][j|k],DP[i][j|k],DP[i][j]+c)
        
    print(-1 if DP[-1][-1]==float('inf') else DP[-1][-1])

if __name__=='__main__':
    main()

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

INF = 10**10
n, m = getList()

dp = [INF for i in range(1<<n)]
dp[0] = 0

for i in range(m):
    a, b = getList()
    cnums = getList()
    state = 0
    for cn in cnums:
        state += 1<<(cn-1)
    
    for i, d in enumerate(dp):
        nstate = i | state
        
        
        if dp[nstate] > dp[i] + a:
            dp[nstate] = dp[i] + a


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

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

N,M=map(int,input().split())
AB=[]
C=[]

for i in range(M):
    AB.append(list(map(int,input().split())))
    C.append(list(map(int,input().split())))
    
DP=[float("inf")]*((1<<N))
DP[0]=0
for i in range(M):
    for j in range(1<<N):
        bitscore=0
        for k in C[i]:
            bitscore+=(1<<(k-1))

        DP[j|bitscore]=min(DP[j]+AB[i][0],DP[j|bitscore])

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

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

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

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

for i in range(M):
    for S in range(1 << N):
        dp[i+1][S | C[i]] = min(dp[i+1][S | C[i]], dp[i][S] + A[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])

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

Solution (Python):
inf = 10**10
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(map(int, input().split()))
    res = 0
    for j in c:
        res+=(1<<(j-1))
    C.append(res)
dp = [[inf]*(2**N) for _ in range(M+1)]
dp[0][0] = 0
for i in range(1, M+1):
    for s in range(2**N):
        print
        dp[i][s] = min(dp[i-1][s], dp[i-1][(s|C[i-1])^C[i-1]]+A[i-1])
ans = dp[M][(1<<N)-1]
print(ans if ans<10**10 else -1)

Solution (Python):

import sys
def input():
	return sys.stdin.readline().strip()



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

ab_list = []
c_list = []

for _ in range(M):
	ab_list.append(tuple(map(int, input().split())))
	c = tuple(map(int, input().split()))
	sum = 0
	for ci in c:
		sum += 2**(ci - 1)
	c_list.append(sum)

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

dp[0][0] = 0

for m in range(0, M):
	for i in range(2**N):
		if dp[m][0] < 10**10:
			loc_next = i | c_list[m]
			dp[m + 1][loc_next] = min(dp[m + 1][loc_next], dp[m][i] + ab_list[m][0])
			dp[m + 1][i] = min(dp[m + 1][i], dp[m][i])

if dp[M][-1] < 10**10:
	print(dp[M][-1])
else:
	print(-1)

Solution (Python):
N, M = map(int, input().split())
afs = []
for i in range(M):
  a, b = map(int, input().split())
  cs = map(int, input().split())
  f = 0
  for c in cs:
    f = f|(1<<(c-1))
  afs.append((a, f))
dp = [{} for i in range(M+1)]
dp[0][0] = 0
for i in range(M):
  d = dp[i]
  a0, f0 = afs[i]
  d2 = {}
  for f in d:
    d2[f] = d[f]
  for f in d:
    f2 = f|f0
    a2 = d[f]+a0
    d2[f2] = a2 if f2 not in d2 else min(d2[f2], a2)
  dp[i+1] = d2

if (1<<N)-1 in dp[M]:
  r = dp[M][(1<<N)-1]
else:
  r = -1
print(r)

Solution (Python):
INF = float('inf')
N,M = map(int,input().split())
A = []
B = []
C = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)

dp = [{} for _ in range(M+1)]
for m in range(M):
    for i in range(2**N):
        if i == 0:
            dp[m][i] = 0
        else:
            dp[m][i] = INF

for m in range(M):
    a = A[m]
    b = B[m]
    c = C[m]
    s = 2**N-1
    for i in range(b):
        s -= 2**(c[i]-1)
    for i in range(2**N):
        dp[m+1][i] = min(dp[m][i],dp[m][i&s]+a)

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

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    N,M = MI()
    money_box = []
    for i in range(M):
        a,_ = MI()
        c=LI()
        bit=0
        for d in c:
            bit += 1<<(d-1)
        money_box.append((a,bit))
    
    bit_max = 1<<N
    dp =[inf]*bit_max
    dp[0] = 0
    for bit_set in range(bit_max):
        for i,(money,bit) in enumerate(money_box):
            before = bit_set-(bit_set&bit)
            dp[bit_set] = min(dp[bit_set],dp[before]+money)
    ans = dp[-1]
    if dp[-1]==inf:
        print(-1)
    else:
        print(dp[-1])
if __name__ == '__main__':
    main()

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

dp = [[float('inf') for _ in range(2 ** N)] for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
    for state in range(2 ** N):
        next_state = state | key[i][1]
        dp[i+1][next_state] = min(dp[i][state] + key[i][0], dp[i+1][next_state])
    for state in range(2 ** N):
        dp[i+1][state] = min(dp[i+1][state], dp[i][state])

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

Solution (Python):
from heapq import heappop,heappush
from operator import or_
from functools import reduce

N,M = map(int,input().split())
def it():
    for _ in range(M):
        a,b = map(int,input().split())
        c = sum(2**(x-1) for x in map(int,input().split()))
        yield (a,c)
boxes = list(it())

end = 2**N-1
check = reduce(or_, (c for a,c in boxes))
if check != end:
    print(-1)
    exit()

cost = [float('inf')]*(2**N)
cost[0] = 0
q = [(0,0)]

while q:
    c,v = heappop(q)
    if cost[v] < c:
        continue
    if v == end:
        break
    for nc,u in boxes:
        nc += c
        u |= v
        if nc < cost[u]:
            heappush(q,(nc,u))
            cost[u] = nc

print(cost[end])

Solution (Python):
n, m = map(int, input().split())
res = [[] for i in range(m)]
val = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(len(c)):
        res[i].append(c[j])
    val[i] = a




INF = 10**9 + 7
dp  = [[INF]*(2**n) for i in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    mask = 0
    for j in res[i]:
        mask += 2**(j-1)
    for bit_state in range(2**n):
        
        dp[i+1][bit_state] = min(dp[i+1][bit_state], dp[i][bit_state])
        
        dp[i+1][bit_state | mask] = min(dp[i+1][bit_state | mask], dp[i][bit_state] + val[i])
if dp[-1][-1] == 10**9 + 7:
    print(-1)
else:
    print(dp[-1][-1])

Solution (Python):
N, M = map(int, input().split())
dp = [0] + [1<<100] * ((1<<N)-1)
for _ in range(M):
    dppre = dp
    a, b = map(int, input().split())
    C = [int(a)-1 for a in input().split()]
    mask = sum([1<<C[i] for i in range(b)])
    for maskpre in range(1<<N):
        new = mask | maskpre
        dp[new] = min(dp[new], dppre[maskpre] + a)
        maskpre -= 1
print(dp[-1] if dp[-1] < (1<<100) else -1)

Solution (Python):

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

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

for i in range(M):

    a,b = map(int,input().split())

    c = list(map(int,input().split()))

    num = 0
    for j in c:
        num += 2 ** (j-1)

    nlis = lis.copy()
    for j in range(2 ** N):

        if lis[j | num] > nlis[j] + a:
            lis[j | num] = nlis[j] + a


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

else:
    print (lis[2 ** N - 1])

Solution (Python):
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
size = 2**N
F = [2**i for i in range(12)]

DP = [10**18] * size
DP[0] = 0

for _ in range(M):
    a, b = inpl()
    X = sum([F[i-1] for i in inpl()])
    
    for i in range(size):
        DP[i|X] = min(DP[i|X], DP[i] + a)

if DP[-1] == 10**18:
    print(-1)
else:
    print(DP[-1])

Solution (Python):
N, M = [int(_) for _ in input().split()]
AS = []
for _ in range(M):
    a, _ = [int(_) for _ in input().split()]
    s = sum(1 << (c - 1) for c in [int(_) for _ in input().split()])
    AS += [(a, s)]
dp = [10**10] * (1 << N)
dp[0] = 0
for S in range(1 << N):
    for a, s in AS:
        dp[S | s] = min(dp[S | s], dp[S] + a)
if dp[-1] == 10**10:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))


dp = [[INF] * (1 << N) for _ in range(M + 1)]
for i in range(M):
    dp[i][0] = 0
for p in range(1 << N):
    dp[0][p] = 0

for i in range(1, M):
    a, b = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))

    pattern = 0
    for c in C:
        pattern += 1 << (c - 1)

    for p in range(len(dp[i])):
        dp[i + 1][p | pattern] = min(
            dp[i + 1][p | pattern],
            dp[i][p] + a
        )
        dp[i + 1][p] = min(
            dp[i + 1][p],
            dp[i][p]
        )

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