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):
INF = 10**9

N, M = map(int, input().split())
key = []
for _ in range(M):
    ab = list(map(int, input().split()))
    box = list(map(int, input().split()))
    index = sum(list(map(lambda x:2**(x-1), box)))
    ab.append(index)
    key.append(ab)
dp = [[key[0][0] if (i & ~key[0][2]) == 0 else INF for i in range(2**N)]]
dp[0][0] = 0
for j in range(1, M):
    next = [0 for _ in range(2**N)]
    for i in range(2**N):
        next[i] = min(dp[j-1][i], dp[j-1][(i & ~key[j][2])]+key[j][0])
    dp.append(next)
if dp[-1][-1] > 10**7:
    print(-1)
else:
    print(dp[-1][-1])

Solution (Python):


f=lambda:map(int,input().split())
N,M=f()
INF=float('inf')

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

def list2int(A):
    res=0
    for a in A:
        res+=2**(a-1)
    return res
    
for m in range(M):
    a,b=f()
    c=list2int(list(f()))
    for i in range(1<<N):
        
        dp[m+1][i|c]=min(dp[m][i]+a,dp[m+1][i|c])
        
        dp[m+1][i]=min(dp[m][i],dp[m+1][i])
res=dp[M][(1<<N)-1]
print(res if res<INF else -1)

Solution (Python):
INF = 10**9

def as_bit(ls):
    
    ret = 0
    for l in ls:
        ret |= 1 << (l - 1)
    return ret

def main():
    
    N, M = map(int, input().split())
    C, A = [], []
    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        c = list(map(int, input().split()))
        C.append(as_bit(c))

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

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [-1 for i in range(2**n)]
    dp[0] = 0

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [-1 for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==-1:
                continue
            new = dp[j]
            
            update = int(curk,2)|j
            
            
            target = temp[update]
            if target==-1:
                temp[update] = new+curc
            elif target>new+curc:
                temp[update] = new+curc                
            if new<temp[j] or temp[j]==-1:
                temp[j] = dp[j]
        dp = temp
        
    print(dp[-1])
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Solution (Python):
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [-1 for i in range(2**n)]
    dp[0] = 0
    
    
    def intersect(bit1,bit2):
        s = ""
        for i in range(n):
            if bit1[i]=="1" or bit2[i]=="1":
                s = "".join([s,"1"])
            else:
                s = "".join([s,"0"])
        return int(s,2)

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [-1 for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==-1:
                continue
            new = dp[j]
            
            s = bin(j)[2:]
            if len(s)!=n:
                while len(s)<n:
                    s = "".join(["0",s])
            update = intersect(curk,s)
            
            
            target = temp[update]
            if target==-1:
                temp[update] = new+curc
            elif target>new+curc:
                temp[update] = new+curc                
            if new<temp[j] or temp[j]==-1:
                temp[j] = dp[j]
        dp = temp
        
    print(dp[-1])
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Solution (Python):
n, m = map(int, input().split())
r = [2**i for i in range(n+1)]

price = [0] * m
mask = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    for box in map(int, input().split()):
        mask[i] += r[box-1]
    price[i] = a


inf = 10**9
dp = [[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 | mask[i]] = min(
            dp[i][j] + price[i],
            dp[i+1][j | mask[i]]
        )
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

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

Solution (Python):
n , m = map(int,input().split())
kagi = []
for i in range(m):
    a , b = map(int,input().split())
    c = list(map(lambda x:int(x)-1,input().split()))
    k = 0
    for j in c:
        k += 2**j
    kagi.append((a,k))
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for j in range(2**n):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j | kagi[i][1]] = min(dp[i+1][j | kagi[i][1]],dp[i][j] + kagi[i][0])

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

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

dp = [INF] * (1 << N)
dp[0] = 0
for i in range(M):
    key_bit = 0
    for k in ks[i]:
        key_bit |= 1 << (k - 1)
    for bit in range((1 << N) - 1, -1, -1):
        if dp[bit] != INF:
            nx_bit = bit | key_bit
            dp[nx_bit] = min(dp[nx_bit], dp[bit] + prices[i])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

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

INF = float("inf")
dp = [[INF] * (2**N) for _ in range(M+1)]
dp[0][0] = 0
for i in range(1, M+1):
    price, value = price_value[i-1]
    for j in range(2**N):
        dp[i][j | value] = min(
            dp[i][j | value], dp[i-1][j] + price
        )
        dp[i][j] = min(dp[i][j], dp[i-1][j])
ans = dp[-1][-1]
print(ans if ans != INF else -1)

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

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

for i in range(M):
  a,b = map(int,readline().split())
  c = list(map(int,readline().split()))
  key = 0
  for j in range(len(c)):
    key += (1 << (c[j] - 1))
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    if j | key == j:
      continue
    if dp[j | key] > dp[j] + a:
      dp[j | key] = dp[j] + a

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

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

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

for i in range(M):
  a,b = map(int,readline().split())
  c = list(map(int,readline().split()))
  key = 0
  for j in range(len(c)):
    key += (1 << (c[j] - 1))
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    if j | key == j:
      continue
    dp[j | key] = min(dp[j | key], dp[j] + a)

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

Solution (Python):
N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C |= (1 << (c - 1))
    Key.append(C)
DP = [float('inf')] * (1 << N)
DP[0] = 0

for cost, key in zip(Cost, Key):
    D = DP[:]
    for i, d in enumerate(DP):
        if d == float('inf'):
            continue
        D[i|key] = min(D[i|key], d + cost)
    DP = D

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

Solution (Python):
N, M = map(int, input().split())
newcount = [100000000 for _ in range(2**N)]
newcount[0] = 0
bi = [1,2,4,8,16,32,64,128,256,512,1024,2048]
for k in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bit = 0
  for k in range(b):
    bit += bi[c[k]-1]
  count = tuple(newcount)
  for k in range(2**N):
    now = bit|k
    newcount[now] = min(newcount[now], a+count[k])
if newcount[-1] < 10**7:
  print(newcount[-1])
else:
  print(-1)

Solution (Python):
N, M = map(int, input().split())
newcount = [float('inf') for _ in range(2**N)]
newcount[0] = 0

for k in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bit = 0
  for k in range(b):
    bit += 2**(c[k]-1)
  count = tuple(newcount)
  for k in range(2**N):
    now = bit|k
    newcount[now] = min(newcount[now], a+count[k])
count = newcount
if count[-1] < 10**6:
  print(count[-1])
else:
  print(-1)

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

Solution (Python):
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()))
    cnt=0
    for j in c:
        cnt+=2**(j-1)
    
    for j in range(2**n):
        dp[j|cnt]=min(dp[j|cnt],dp[j]+a)


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

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

Solution (Python):
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, M = read_ints()
    
    cover = [0]*M
    
    costs = [0]*M
    INF = 10**9+1
    for i in range(M):
        a, b = read_ints()
        costs[i] = a
        for c in read_ints():
            cover[i] |= 1<<(c-1)
    
    mask_to_cost = [INF]*(1<<N)
    mask_to_cost[0] = 0
    for mask in range(1<<N):
        for i in range(M):
            mask_to_cost[cover[i]|mask] = min(mask_to_cost[cover[i]|mask], mask_to_cost[mask]+costs[i])
    return mask_to_cost[(1<<N)-1] if mask_to_cost[(1<<N)-1] != INF else -1


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

Solution (Python):








def solve(N, M, ABCi):
    inf = 10 ** 5 * 12 * 2
    for i in range(M):
        C = ABCi[i][2]
        ABCi[i][2] = sum([2 ** (c - 1) for c in C])
    
    dp = [[inf] * (2 ** N) for _ in range(M + 1)]
    dp[0][0] = 0
    for i in range(1, M + 1):
        for j in range(2 ** N):
            a, b, c = ABCi[i - 1]
            dp[i][j] = min(dp[i - 1][(c & j) ^ j] + a, dp[i - 1][j])
    ans = min([x[2 ** N - 1] for x in dp])
    if ans == inf:
        ans = -1
    print(ans)


if __name__ == '__main__':
    N, M = map(int, input().split())
    ABCi = [
        [int(i) for i in input().split()] + [[int(i) for i in input().split()]]
        for _ in range(M)]
    solve(N, M, ABCi)

Solution (Python):



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

dp=[10**10]*2**N
dp[0]=0

for _ in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    
    can_open=sum([2**(c[i]-1) for i in range(len(c))])
    
    for i in range(len(dp))[::-1]:
        if dp[i]!=10**10 and i|can_open<2**N:
            dp[i|can_open]=min(dp[i]+a,dp[i|can_open])


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

Solution (Python):
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  for i in range(m):
    a,b=map(int,input().split())
    t=sum([1<<(int(x)-1) for x in input().split()])
    for s in range(1<<n):
      dp[t|s]=dp[t|s] if dp[t|s]<=dp[s]+a else dp[s]+a
  print(-1 if dp[-1]==inf else dp[-1])
  
  
if __name__=='__main__':
  main()

Solution (Python):
def min(a,b):
  return a if a<=b else b


def main():
  n,m=map(int,input().split())
  inf=10**9
  cost=[0]*m
  dp=[inf]*(1<<n)
  dp[0]=0
  for i in range(m):
    a,b=map(int,input().split())
    t=sum([1<<(int(x)-1) for x in input().split()])
    for s in range(1<<n):
      dp[t|s]=min(dp[t|s], dp[s]+a)
  print(-1 if dp[-1]==inf else dp[-1])
  
  
if __name__=='__main__':
  main()

Solution (Python):
n, m = map(int, input().split())
a = []
b = []
c = []
checker = [0]*n
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(int, input().split()))
    ci_int = 0
    for hako in ci:
        hako -= 1
        ci_int += 2**hako
        if checker[hako] == 0:
            checker[hako] = 1
    a.append(ai)
    b.append(bi)
    c.append(ci_int)



if sum(checker) != n:
    print(-1)
    exit()

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


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

Solution (Python):
import copy
N, M = map(int, input().split())
key = [0] * M
bin_max = (2 ** N) 
dp = [[float('inf')] * (bin_max) ]
for i in range(M):
  a, _ =  map(int, input().split())
  c = list(map(int, input().split()))
  temp = 0
  for j in c:
    temp += (1 << (j-1))
  key[i] = ([a,temp])
  
for i in range(0,M):
  b = key[i][1]
  value = key[i][0]
  dp_low = copy.copy(dp[i])
  for j in range(1,bin_max):
    if j & b == j and dp_low[j] > value:
      dp_low[j] = value
    if dp_low[j] != float('inf'):
      next_b = j | b
      next= dp_low[j] + value
      if dp_low[next_b] > next:
        dp_low[next_b] = next
  dp.append(dp_low)
ans = -1 if dp[M-1][bin_max - 1] == float('inf') else dp[M-1][bin_max - 1]
print(ans)

Solution (Python):
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  
  
  for i in range(m):
    a,b=map(int,input().split())
    c=[1<<(int(x)-1) for x in input().split()]
    t=sum(c)
    
    for s in range(1<<n):
      if dp[t|s]>dp[s]+a:
        dp[t|s]=dp[s]+a
      
    
  
  """
  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  
  """
  
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Solution (Python):
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  
  
  for i in range(m):
    a,b=map(int,input().split())
    c=[1<<(int(x)-1) for x in input().split()]
    t=sum(c)
    
    for s in range(1<<n):
      dp[t|s]=min(dp[t|s], dp[s]+a)
    
  
  """
  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  
  """
  
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Solution (Python):
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  
  
  for i in range(m):
    a,b=map(int,input().split())
    c=[int(x)-1 for x in input().split()]
    t=0
    for j in c:
      t|=1<<j
    
    for s in range(1<<n):
      dp[t|s]=min(dp[t|s], dp[s]+a)
    
  
  """
  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  
  """
  
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Solution (Python):
def main():
  n,m=map(int,input().split())
  inf=10**9
  cost=[inf for i in range(m)]
  for i in range(m):
    a,b=map(int,input().split())
    c=[int(x)-1 for x in input().split()]
    s=0
    for j in c:
      s|=1<<j
    cost[i]=[s,a]
  

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

if __name__=='__main__':
  main()

Solution (Python):
n,m=map(int,input().split())
inf=10**9
cost=[inf for i in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  c=[int(x)-1 for x in input().split()]
  s=0
  for j in c:
    s|=1<<j
  cost[i]=[s,a]


dp=[inf]*(1<<n)
dp[0]=0
for s in range(1<<n):
  for bit,c in cost:
    dp[s|bit]=min(dp[s|bit], dp[s]+c)

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

Solution (Python):
n, m = map(int, input().split())
dp = [float("inf") for i in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    num = 0
    for j in range(b):
        num += 2 ** (c[j] - 1)
    for k in range(2 ** n):
        dp[k | num] = min(dp[k | num], dp[k] + a)
if dp[2 ** n - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** n - 1])

Solution (Python):
import sys



def input():
    return sys.stdin.readline().rstrip()


def main():
    N, M = map(int, input().split())

    dp = [10 ** 9] * pow(2,N)
    dp[0] = 0

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

    print(dp[-1] if dp[-1] !=10**9 else -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()))
  bi=0
  for i in c:
    bi+=1<<(i-1)
  key.append([a,bi])


INF=2**24
dp=[INF]*(1<<n)
dp[0]=0
for k in key:
  for b in range(1<<n):
    dp[b|k[1]]=min(dp[b|k[1]],dp[b]+k[0])
    
    
print(-1 if dp[-1]==INF else dp[-1])

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()))
    v = 0
    for i in range(b):
        v += 1 << (c[i] - 1)
    key.append([a, v])

dp = [[float('inf')] * (1<<n) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    money, value = key[i]
    for j in range(1<<n):
        dp[i+1][j|value] = min(dp[i+1][j|value], dp[i][j] + money)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

Solution (Python):
import math

N, M = map(int, input().split())
dp = [math.inf] * pow(2, N)  
dp[0] = 0
for _ in range(M):
    a, b = map(int, input().split())
    c = sum([pow(2, int(i)-1) for i in input().split()])
    for i in range(pow(2, N)):
        dp[i | c] = min(dp[i | c], dp[i] + a)
print(dp[-1] if dp[-1]!=math.inf else -1)

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

INF = float("inf")



dp = [INF] * (2**N)

dp[0] = 0

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

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

    
    
    
    
    
    
    for j in range(2**N):
        
        target = j | tmp
        
        dp[target] = min(dp[j] + a, dp[target])


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

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

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = []
    C = []
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        c = [int(x) for x in input().split()]
        tmp = 0
        for cc in c:
            tmp |= 1 << (cc - 1)

        C.append(tmp)

    dp = [float("inf")] * (2 ** N + 1)

    dp[0] = 0

    for i in range(M):
        for k in range(2 ** N + 1):
            next = C[i] | k
            if next >= (2 ** N + 1):
                continue
            dp[next] = min(dp[next], dp[k] + A[i])

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


if __name__ == '__main__':
    main()

Solution (Python):
import math

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

keys = []

for i in range(M):
    a, b = list(map(int, input().split()))
    key_bit = 0
    c = list(map(int, input().split()))
    for j in range(b):
        key_bit |= 1 << (c[j] - 1)
    keys.append([a, key_bit])

dp = [math.inf]*(1 << N)

dp[0] = 0

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

if dp[-1] == math.inf:
    dp[-1] = -1

print(dp[-1])

Solution (Python):

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

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

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

    for s in range(1 << N):
        for i in range(M):
            ns = s | Box_key[i][0]
            cost = dp[s] + Box_key[i][1]
            dp[ns] = min(dp[ns], cost)

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


if __name__ == "__main__":
    resolve()

Solution (Python):

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

    Cost = [0] * M
    Box_key = [0] * M
    for i in range(M):
        a, b = map(int, input().split())
        Cost[i] = a
        C = list(map(int, input().split()))
        Box_key[i] = sum(1 << (c - 1) for c in C)

    
    
    dp = [[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 + 1][j], dp[i][j])
            dp[i + 1][j | Box_key[i]] = min(dp[i + 1][j | Box_key[i]], dp[i][j] + Cost[i])

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


if __name__ == "__main__":
    resolve()

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

dp=[2**100 for i in range(2**n)]
dp[0]=0
for i in k:
  for j in range(2**n):
    dp[i[1]|j]=min(dp[i[1]|j],dp[j]+i[0])
if dp[-1]==2**100:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
def f(L):
    X=0
    for k in L:
        X+=2**(k-1)
    return X

N,M=map(int,input().split())
H=2**N
inf=float("inf")

DP=[inf for _ in range(H)]
DP[0]=0

for _ in range(M):
    A,B=map(int,input().split())
    C=f(list(map(int,input().split())))

    for k in range(H):
        DP[k|C]=min(DP[k|C],DP[k]+A)

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

Solution (Python):
n,m=map(int,input().split())
ans=[float("inf")]*(2**n)
ans[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    tmp=0
    for j in c:
        tmp+=2**(j-1)
    na=ans.copy()
    for j in range(2**n):
        if ans[j|tmp]>na[j]+a:
            ans[j|tmp]=na[j]+a
if ans[2**n-1]==float("inf"):
    print(-1)
else:
    print(ans[2**n-1])

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import itertools
    
    mod=10**9+7
    N,M=MI()
    a=[0]*M
    b=[0]*M
    c=[]
    
    for i in range(M):
        a[i],b[i]=MI()
        cc=LI()
        for j in range(b[i]):
            cc[j]-=1
        c.append(cc)
        
    N2=pow(2,N)
    inf=10**10
    
    def encode(L):
        temp=0
        for i in range(len(L)):
            temp+=L[i]<<i
        return temp
            
    
    dp=[[inf]*N2 for _ in range(M+1)]
    
    
    dp[0][0]=0
    for i in range(M):
        for ite in itertools.product([0,1], repeat=N):
            L=list(ite)
            j=encode(L)
            for k in c[i]:
                L[k]=1
            nj=encode(L)
            
            if dp[i][j]!=inf:
                dp[i+1][j]=min(dp[i+1][j], dp[i][j])
                dp[i+1][nj]=min(dp[i+1][nj], dp[i][j]+a[i])
        
    ans=dp[-1][-1]
    if ans==inf:
        ans=-1
    print(ans)
    
    
    
                
    

main()

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

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


def unset_nth_bit(S, j):
    
    return S & ~(1 << j)

def set_nth_bit(S, j):
    
    return S | (1 << j)

def bit(S, j):
    
    return (S>>j)&1

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

a = []
c = []
for i in range(M):
    p, q = map(int, input().split())
    a.append(p)
    c.append(list(map(int, input().split())))

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

for i in range(M):
    for S in range(1<<N):
        SS = S
        for cc in c[i]:
            SS = set_nth_bit(SS, cc-1)
        dp[i+1][SS] = min(dp[i+1][SS], dp[i][S] + a[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])

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

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()))
  bi=0
  for i in c:
    bi+=2**(i-1)
  key.append([a,bi])
dp=[10**10]*(2**n)
dp[0]=0
for k in key:
  for b in range(2**n):
    dp[b|k[1]]=min(dp[b|k[1]],dp[b]+k[0])
if dp[-1]==10**10:
  print(-1)
else:
  print(dp[-1])

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

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

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

for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    T = 0
    
    for ci in c:
        T += 1<<(ci-1)
    
    ks.append((a, T))

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

for S in range(1<<N):
    for a, T in ks:
        dp[S|T] = min(dp[S|T], dp[S]+a)

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

Solution (Python):
n, m = map(int, input().split())
dp = [float("inf") for i in range(1 << n)]
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for j in range(b):
        bit |= 1 << (c[j] - 1)
    for j in range(1 << n):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == float("inf"):
    print("-1")
else:
    print(dp[-1])

Solution (Python):
n,m=map(int,input().split())
a=[None]*m
b=[None]*m
c=[None]*m
for i in range(m):
  a[i],b[i]=map(int,input().split())
  c[i]=list(map(int,input().split()))
INF=10**18
dp=[INF for _ in  range(1<<n)]
dp[(1<<n)-1]=0
for bit in range((1<<n)-2,-1,-1):
  for u in range(m):
    dumy=bit
    flag=0
    for i in c[u]:
      i-=1
      if not ((bit>>i) & 1):
        dumy|=(1<<i)
        flag=1
    if flag:
      dp[bit]=min(dp[bit],dp[dumy]+a[u])
print([dp[0],-1][dp[0]==INF])

Solution (Python):



INF = 10**6

n, m = map(int, input().split())
dp = [INF] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    bit = ['0'] * n
    for x in set(map(int, input().split())):
        bit[x-1] = '1'
    bit = int(''.join(bit), 2)
    for j in range(2**n-1, -1, -1):
        dp[j|bit] = min(dp[j|bit], a + dp[j])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Solution (Python):



INF = 10**6

n, m = map(int, input().split())
dp = [INF] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    bit = ['0'] * n
    for x in set(map(int, input().split())):
        bit[x-1] = '1'
    bit = int(''.join(bit[::-1]), 2)
    for j in range(2**n-1, -1, -1):
        dp[j|bit] = min(dp[j|bit], a + dp[j])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
"""
bitDP
dp[j] => jの二進数表記で1になっている桁数と同じ番号の宝箱を全て開けるのに必要な費用の最小値
"""

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

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

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

Solution (Python):
from collections import defaultdict
INF = 10**13
N, M = map(int, input().split())
A = []
C = []
for m in range(M):
    a, b = map(int, input().split())
    A += [a]
    c = list(map(int, input().split()))
    C += [sum(map(lambda x: 2**(x-1), c))]
dp = [INF 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] + A[j], dp[i | C[j]])

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