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
readline = sys.stdin.readline

N,M = map(int,readline().split())
keys = [None] * M
for i in range(M):
  cost,b = map(int,readline().split())
  bit = 0
  target = list(map(int,readline().split()))
  for t in target:
    bit += (1 << (t - 1))
  keys[i] = (cost, bit)
    

INF = 10 ** 8 + 1
dp = [INF for i in range(2 ** N)]
dp[0] = 0
for key in keys:
  cost, bit = key
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == -1:
      continue
    if dp[j | bit] > dp[j] + cost:
      dp[j | bit] = dp[j] + cost

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, M = getNM()
dp = [float("inf")] * (1 << N)
dp[0] = 0



for i in range(M):
    a, b = getNM()
    c = getList()
    bit = 0
    
    for item in c:
        bit |= (1 << (item - 1))
    
    
    for j in range(1 << N):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)

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

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

dp = [1000000000 for i in range(2**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])
if dp[2**n-1]==1000000000:
  print(-1)
else:
  print(dp[2**n-1])

Solution (Python):
def chmin(l, i, v):
  if l[i] > v:
    l[i] = v
    return True
  return False

def main():
    N, M = map(int, input().split())
    keys = []
    for i in range(M):
        a, b = map(int, input().split())
        C = map(int, input().split())
        
        mask = 0
        for c in C:
            mask |= 1 << (c-1)
        keys.append((a, mask))
    
    
    
    patterns = 1 << N
    INF = float("inf")
    
    
    dp = [ INF ] * patterns
    dp[0] = 0

    
    for a, mask in keys:
        for i in range(patterns):
            chmin(dp, i|mask, dp[i] + a)

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

if __name__ == '__main__':
    main()

Solution (Python):
INF = 10**18

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

A = []
B = []
C = []

for _ in range(M):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)
    c = tuple(map(int,input().split()))
    C.append(c)
    
dp = [[INF for j in range(2**N)] for i in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    s = 0
    for k in range(B[i]):
        s += 2**(C[i][k] - 1)
    for j in range(2**N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | s] = min(dp[i + 1][j | s], dp[i][j] + A[i])
        
res = dp[M][2**N - 1]

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

Solution (Python):
N, M = map(int, input().split())
keys = []
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  s = 0
  for cc in c:
    cc -= 1
    s |= 1<<cc
  keys += [(s, a)]

dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | keys[i][0]
    dp[t] = min(dp[t], keys[i][1]+dp[s])

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

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

dp = [10**10 for B in range(1 << N)]
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = [int(j) for j in input().split()]
    C = sum([1 << (x-1) for x in c])

    for B in range(1 << N):
        dp[B | C] = min(dp[B | C], dp[B]+a)

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

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

dp = [[10**10 for B in range(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(j) for j in input().split()]
    C = sum([1 << (x-1) for x in c])

    for B in range(1 << N):
        dp[i+1][B] = min(dp[i][B], dp[i+1][B])
        dp[i+1][B | C] = min(dp[i+1][B | C], dp[i][B]+a)

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

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

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

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

    if dp[2**N - 1] == INF:
        ans = -1
    else:
        ans = dp[2**N - 1]

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

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

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

    if dp[2**N - 1] == INF:
        ans = -1
    else:
        ans = dp[2**N - 1]

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
def main():
  N, M = map(int, input().split())
  inf =  10**9
  p = 1<<N
  dp = [inf]*p 
  dp[0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([1<<(c-1) for c in C])
    for j in range(p):
      
      dp[j|c_bit] = min(dp[j|c_bit], dp[j] + a)
  if dp[p-1] == inf:
    print(-1)
  else: 
    print(int(dp[p-1]))
  
if __name__ == "__main__":
  main()

Solution (Python):
def main():
  N, M = map(int, input().split())
  inf =  10**15
  p = 1<<N
  dp = [inf]*p
  dp[0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    c = sum(1<<(i-1) for i in map(int, input().split()))
    for j in range(p):
      dp[c|j] = min(dp[j]+a, dp[c|j])
  if dp[-1] == inf:
    print(-1)
  else: 
    print(int(dp[-1]))
  
if __name__ == "__main__":
  main()

Solution (Python):
N, M = map(int, input().split())
inf =  10**9
dp = [[inf]*2**N for _ in range(M+1)]
for i in range(M+1):
  dp[i][0] = 0

def main():
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([2**(c-1) for c in C])
    for j in range(2**N):
      if dp[i][j] == inf:
        continue
      else:
        
        dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()

Solution (Python):



import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline




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_)
    val = 0
    for _c_ in c_:
        val += 2 ** (_c_ -1)
    c.append(val)

max_m = 2**n

dp = [[float('inf')] * max_m for _ in range(m+1)]
dp[0][0]=0



for i in range(1, m+1):
    for combi in range(max_m):
        
        combi_diff = 0
        combi_diff = combi & ~c[i-1]
        dp[i][combi] = min(dp[i-1][combi], dp[i-1][combi_diff] + a[i-1])

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

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

dp = [[10**10 for _ in range(2**n)] for j in range(m)]
dp[0][0] = 0
a, b = map(int, input().split())
c = list(map(int, input().split()))
idx = 0
for cc in c:
  idx += 2**(cc-1)
for j in range(1, 2**n):
  if ~idx & j == 0:
    dp[0][j] = a

for i in range(1, m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  idx = 0
  for cc in c:
    idx += 2**(cc-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j], dp[i-1][(j|idx)^idx]+a)

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

Solution (Python):
from functools import reduce
N, M = map(int, input().split())
L = 1 << N
table = {0: 0}
for _ in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l, now in table.copy().items():
        table[l | match] = min(now + cost, table.get(l | match, 10 ** 7))
print(table[L - 1] if table.get(L - 1, False) else -1)

Solution (Python):
from functools import reduce
N, M = map(int, input().split())
L = 1 << N
table = {0: 0}
for _ in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l, now in table.copy().items():
        table[l | match] = min(now + cost, table.get(l | match, 10 ** 7))
print(table[L - 1] if table.get(L - 1, False) else -1)

Solution (Python):
from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
table = [INF] * L
table[0] = 0
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l in range(L):
        now = table[l]
        if l and not now:
            continue
        table[l | match] = min(now + cost, table[l | match])
print(table[L - 1] if table[L - 1] != INF else -1)

Solution (Python):
from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
table = [[INF] * L for _ in range(M + 1)]
table[0][0] = 0
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l in range(L):
        now = table[m][l]
        if l and not now:
            continue
        table[m + 1][l] = min(now, table[m + 1][l])
        table[m + 1][l | match] = min(now + cost, table[m + 1][l | match])
print(table[M][L - 1] if table[M][L - 1] != INF else -1)

Solution (Python):
from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
keys = [0] * M
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    keys[m] = cost, match
table = [[INF] * L for _ in range(M + 1)]
table[0][0] = 0
for m in range(M):
    cost, match = keys[m]
    for l in range(L):
        now = table[m][l]
        if l and not now:
            continue
        table[m + 1][l] = min(now, table[m + 1][l])
        table[m + 1][l | match] = min(now + cost, table[m + 1][l | match])
print(table[M][L - 1] if table[M][L - 1] != INF else -1)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [INF for i in range(k)]
dp[0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    dpnew = dp[:]
    for j in range(k):
        dpnew[j|d] = min(dp[j]+a,dpnew[j|d])
    dp = dpnew

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [INF]*k 
dp[0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    dpnew = dp[:]
    for j in range(k):
        dpnew[j|d] = min(dp[j]+a,dpnew[j|d])
    dp = dpnew

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [INF]*k 
dp[0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    dpnew = dp[:]
    for j in range(k):
        dpnew[j|d] = min(dp[j]+a,dpnew[j|d])
    dp = dpnew

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [[INF]*k for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    for j in range(k):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [[INF]*k for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(2**(ci-1) for ci in c)
    for j in range(k):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [[INF]*k for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(2**(ci-1) for ci in c)
    for j in range(k):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
dp = [[INF]*(2**N) for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(2**(ci-1) for ci in c)
    for j in range(2**N):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

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

Solution (Python):

N, M = [int(i) for i in input().split()]
key = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    cs = [int(_) for _ in input().split()]
    s = 0
    for c in cs:
        c -= 1
        s |= 1 << c
    key.append([s, a])

INF = 10**9
dp = [INF for i in range(2**N)]
dp[0] = 0
for i in range(2**N):
    for j in range(M):
        t = i | key[j][0]
        cost = key[j][1]
        dp[t] = min(dp[t], dp[i] + cost)
ans = dp[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

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

Solution (Python):
n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << c-1
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
N, M = map(int, input().split()) 
asl = []
for _ in range(M):
    a, b = map(int, input().split()) 
    cl = list(map(int, input().split())) 
    s = 0
    for c in cl:
        s += 1<<(c-1)
    asl.append([a,s])

INF = 10**8
dp = [INF]*(2**N)
dp[0] = 0
for i in range(2**N):
    for as_v in asl:
        a, s = as_v
        dp[i|s] = min(dp[i]+a ,dp[i|s])

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

Solution (Python):
N,M = (int(x) for x in input().split())
abc = [[None] * 3 for _ in range(M)]
check = set()
for x in abc:
    x[0],x[1] = (int(x) for x in input().split())
    x[2] = list(map(int, input().split()))
    check = check | set(x[2])
if len(check) < N:
    print('-1')
else:
    a = [x[0] for x in abc]
    c = [0] * (M+1)
    dp = [[float('inf')] * pow(2,N) for _ in range(M+1)]
    for i in range(1,M+1):
        c[i] = sum(pow(2,y-1) for y in abc[i-1][2])
    for i in range(M+1):
        dp[i][0] = 0
    for i in range(1,M+1):
        for j in range(pow(2,N)):
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            dp[i][j|c[i]] = min(dp[i][j|c[i]],dp[i][j]+a[i-1])
    print(dp[M][pow(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,b = map(int,input().split())
    A[i] = a
    for j in map(int,input().split()):
        j -= 1
        C[i] += 1<<j 

dp = [[INF]*(m+1) for _ in range(1<<n)]
dp[0][0] = 0
for i in range(1<<n):
    for j in range(m):
        dp[i][j+1] = min(dp[i][j],dp[C[j]&i^i][j] + A[j])


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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    dp = [10**10 for _ in [0]*(2**n)]
    dp[0] = 0
    for _ in range(m):
        a,b = map(int,ipt().split())
        c = [int(i) for i in ipt().split()]
        opn = 0
        for i in c:
            opn += 2**(i-1)
        for i in range(2**n):
            if i&opn == 0:
                continue
            elif dp[i] > dp[i-(i&opn)]+a:
                dp[i] = dp[i-(i&opn)]+a

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

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
dp=[10**10]*(1<<N)
dp[0]=0
for i in range(M):
  a,b=map(int,input().split()) 
  c=list(map(int, input().split()))
  d=0
  for j in c:
    d|=1<<j-1
  for k in range(1<<N):
    dp[k|d]=min(dp[k|d],dp[k]+a)
if dp[-1]==10**10:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
inf = 10 ** 9
dp = [0] + [inf] * ((1 << n) - 1)
for _ in range(m):
    newdp = [p for p in dp]
    a, b = map(int, input().split())
    c = sum(1 << (int(i) - 1) for i in input().split())
    for bits in range(len(dp)):
        newdp[bits | c] = min(newdp[bits | c], dp[bits] + a)
    dp = newdp
print(-1 if dp[-1] == inf else dp[-1])

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

dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    SS = sum([1 << (cc - 1) for cc in c])
    for S in range(1 << n):
        dp[S | SS] = min(dp[S | SS], dp[S] + a)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N,M = map(int,input().split())

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

        bit = 0
        for c in set(map(int,input().split())):
            bit += 1<<(c-1)

        key.append((a,bit)) 

    dp = [[INF] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(2**N):
            cost,bit = key[i]

            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            dp[i+1][j|bit] = min(dp[i+1][j|bit],dp[i][j] + cost)

    last = dp[-2][-1]
    print(last if 0 < last < INF else -1)



if __name__ == "__main__":
  main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    dp=[10**10]*(1<<n)
    dp[0]=0
    for i in range(m):
        a,b=map(int,input().split())
        C=list(map(int,input().split()))
        d=0
        for c in C:
            d|=1<<(c-1)
        for j in range(1<<n):
            dp[j|d]=min(dp[j|d],dp[j]+a)
    if dp[-1]==10**10:
        print(-1)
    else:
        print(dp[-1])
        
if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    dp=[10**10]*(1<<n)
    dp[0]=0
    for i in range(m):
        a,b=map(int,input().split())
        C=list(map(int,input().split()))
        d=0
        for c in C:
            d|=1<<(c-1)
        for j in range(1<<n):
            dp[j|d]=min(dp[j|d],dp[j]+a)
    if dp[-1]==10**10:
        print(-1)
    else:
        print(dp[-1])
        
if __name__=='__main__':
    main()

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()

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

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        m = i|c
        dp[m] = min(dp[m],dp[i]+a)

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

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()

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

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

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()

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

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for (a,b),c in zip(AB,C):
        dp[i|c] = min(dp[i|c],dp[i]+a)

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

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()

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

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

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

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()

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

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

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

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

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()

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

dp = [float('inf')]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

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

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

status_count = pow(2, N)
INF = 10 ** 30

dp = [INF] * (status_count)
dp[0] = 0
for a, c in key:
    
    for i in range(status_count):
        dp[i | c] = min(dp[i | c], dp[i] + a)

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

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    INF = float('inf')
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    dp = [[INF] * (1 << n) for _ in range(m)]

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

        dp[i][0] = 0

        tmp = 0
        for ci in c:
            tmp |= 1 << (ci - 1)

        if i == 0:
            dp[i][tmp] = a
        else:
            for j in range(1 << n):
                dp[i][j] = min(dp[i][j], dp[i - 1][j])
                dp[i][j | tmp] = min(dp[i][j | tmp], dp[i - 1][j] + a)

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):


def compute(subset):
	r = 0
	for i in range(len(subset)):
		r +=  (1 << (subset[i]-1))
	return r	

n,m = map(int, raw_input().split(' '))
keys= []
for _ in range(m):
	cost, nk = map(int, raw_input().split(' '))
	keys.append((cost, compute( map(int, raw_input().split(' ')) )))

h = {0:0}
for cost,mask in keys:
	for uu in range(2 ** n - 1,-1,-1):
		cm = uu & mask
		cm = uu ^ (cm) 
		h[uu] = min(h[uu] if uu in h else +float('inf'), (h[cm] if cm in h else +float('inf')) + cost )
print h[2 ** n -1] if (2 ** n -1) in h and h[(2 ** n) -1] < float('inf') else -1

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

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

for i in range(1, M+1):
    for j in range(2**N):
        k = Cost[i-1][0] | j
        dp[i][j] = min(dp[i-1][j], dp[i][j])
        dp[i][k] = min([dp[i-1][j] + Cost[i-1][1], dp[i-1][k], dp[i][k]])

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

Solution (Python):
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,M = map(int,(input().split()))
dp = [float("inf")]*(2**N)
dp[0] = 0
for i in range(M):
    a,b = map(int,(input().split()))
    c = list(map(int,(input().split())))
    d = 0
    for j in c:
        d += 2**(j-1)
    for j in range(2**N):
        dp[j|d] = min(dp[j|d],dp[j]+a)

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

Solution (Python):
def main():
  n, m = map(int, input().split())
  
  dp = [0]*(2**n)
  len_dp = len(dp)

  key_list = dict()
  sub = 1
  for i in range(n):
    key_list[i+1] = sub
    sub *= 2

  for _ in range(m):
    a, b = map(int, input().split())
    c = [int(x) for x in input().split()]
    key = 0
    for value in c:
      key += key_list[value]
    for i in range(len_dp-1, -1, -1):
      if i == 0 or dp[i]:
        if dp[i|key]:
          dp[i|key] = min([dp[i]+a, dp[i|key]])
        else:
          dp[i|key] = dp[i]+a

  print(dp[len_dp-1] if dp[len_dp-1] else -1)

if __name__ == "__main__":
  main()

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

B = [INF]*(1<<n)
B[0] = 0

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

if B[(1<<n)-1]==INF:
  print(-1)
else:
  print(B[(1<<n)-1])

Solution (Python):
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
lst=[0]*M
for i in range(M):
 a,b=map(int,input().split())
 c=set(map(int,input().split()))
 d=0
 for n in c:
  d+=2**(n-1)
  lst[i]=(a,d)
ans=[[float("inf") for e in range(2**N)] for f in range(M+1)]
ans[0][0]=0
for j in range(M):
 for i in range(2**N):
  e= i-(lst[j][1]&i)
  ans[j+1][i]=min(ans[j][e]+lst[j][0],ans[j][i])
if ans[M][2**N-1]==float("inf"):
 print(-1)
else:
 print(ans[M][2**N-1])

Solution (Python):
N,M=map(int,input().split())
lst=[0]*M
for i in range(M):
 a,b=map(int,input().split())
 c=list(map(int,input().split()))
 d=0
 for n in range(b):
  d+=2**(c[n]-1)
  lst[i]=(a,d)
ans=[[float("inf") for e in range(2**N)] for f in range(M+1)]
ans[0][0]=0
for j in range(M):
 for i in range(2**N):
  e= i-(lst[j][1]&i)
  ans[j+1][i]=min(ans[j][e]+lst[j][0],ans[j][i])
if ans[M][2**N-1]==float("inf"):
 print(-1)
else:
 print(ans[M][2**N-1])