Problem:
 Score : 500 points    Problem Statement We have N locked treasure boxes, numbered 1 to N .  A shop sells M keys. The i -th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1} , c_{i2} , ... , c_{i{b_i}} . Each key purchased can be used any number of times.  Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1 .      Constraints  All values in input are integers.  1 \leq N \leq 12  1 \leq M \leq 10^3  1 \leq a_i \leq 10^5  1 \leq b_i \leq N  1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  c_{11}  c_{12}  ...  c_{1{b_1}}  :  a_M  b_M  c_{M1}  c_{M2}  ...  c_{M{b_M}}       Output Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1 .        Sample Input 1 2 3
10 1
1
15 1
2
30 2
1 2      Sample Output 1 25  We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.       Sample Input 2 12 1
100000 1
2      Sample Output 2 -1  We cannot unlock all the boxes.       Sample Input 3 4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3      Sample Output 3 69942

Solution (Python):
N,M = map(int,input().split())
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()))
  key = 0
  for j in range(len(c)):
    key += (1 << (c[j] - 1))
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    dp[j | key] = min(dp[j | key], dp[j] + a)

print((dp[-1], -1)[dp[-1] == INF])

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



n,m=map(int,input().split())
k=2**n
inf=10**7
d=[[inf]*k for _ in range(m+1)]
for i in range(m+1):
  d[i][0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    res=0
    for x in c:
        res+=2**(x-1)
    for j in range(2**n):
        jx=j|res
        d[i+1][j]=min(d[i+1][j],d[i][j])
        d[i+1][jx]=min(d[i][jx],d[i][j]+a,d[i+1][jx])
if d[-1][-1]==10**7:
  print(-1)
else:
  print(d[-1][-1])

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

n, m = map(int, input().split())
ac = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    ac.append((a, c))


dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, ci) in enumerate(ac, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])

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

n, m = map(int, input().split())
abc = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    abc.append([a,b,c])


dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, _, ci) in enumerate(abc, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])

Solution (Python):
import sys

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


def resolve():
    n, m = map(int, input().split())
    A, C = [], []
    for _ in range(m):
        a, b = map(int, input().split())
        A.append(a)
        key = 0
        for c in map(int, input().split()):
            key |= 1 << (c - 1)
        C.append(key)

    dp = [f_inf] * (1 << n)
    dp[0] = 0
    for S in range(1 << n):
        for i in range(m):
            key, cost = C[i], A[i]
            dp[S | key] = min(dp[S | key], dp[S] + cost)
    print(dp[-1] if dp[-1] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], _ = map(int, input().split())
        C[i] = sum(2 ** (int(c) - 1) for c in input().split())

    INF = 10 ** 18
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for a, c in zip(A, C):
        for s in range(2 ** N):
            dp[s | c] = min(dp[s | c], dp[s] + a)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
bs = [None]*m
a = [None]*m
for i in range(m):
    a[i],_ = map(int, input().split())
    c = list(map(int, input().split()))
    b = 0
    for num in c:
        b += 1<<(num-1)
    bs[i] = b
dp = [[float("inf")]*(1<<n) for _ in range(m+1)]
for i in range(m+1):
    dp[i][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])
        b = j | bs[i]
        dp[i+1][b] = min(dp[i+1][b], dp[i][j]+a[i])
ans = dp[m][(1<<n)-1]
if ans==float("inf"):
    ans = -1
print(ans)

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


def main():
    n, m = map(int, input().split())
    price = [0]*m
    typesnum = [0]*m
    keybit=[0]*m
    for i in range(m):
        price[i], typesnum[i] = map(int, input().split())
        keybit[i] = sum(map(lambda x: 2**(int(x)-1), input().split()))
    dp = [10**9]*(1 << n)
    dp[0]=0
    for bit in range(1 << n):
        for i in range(m):
            dp[bit | keybit[i]] = min(dp[bit | keybit[i]], dp[bit]+price[i])
    if dp[-1] == 10**9:
        dp[-1] = -1
    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())
    price = [0]*m
    typesnum = [0]*m
    types = [[] for _ in range(m)]
    for i in range(m):
        price[i], typesnum[i] = map(int, input().split())
        types[i] = list(map(lambda x: int(x)-1, input().split()))
    dp = [10**9]*(1 << n)
    dp[0]=0
    for bit in range(1 << n):
        for i in range(m):
            keybit = 0
            for op in types[i]:
                keybit |= 1 << op
            dp[bit | keybit] = min(dp[bit | keybit], dp[bit]+price[i])
    if dp[-1] == 10**9:
        dp[-1] = -1
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
inf = 10 ** 10
dp = [inf for _ in range(2 ** n)]
dp[0] = 0
bin_s = [2 ** i for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    clst = list(map(int, input().split()))
    tmp = 2 ** n - 1
    for c in clst:
        tmp -= bin_s[c - 1]
    for i in range(2 ** n):
        dp[i] = min(dp[i], dp[i & tmp] + a)

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

Solution (Python):
N,M = map(int,input().split())
key = []
for i in range(M):
  a,b = map(int,input().split())
  C = list(map(int,input().split()))
  s = 0
  for i in range(b):
    C[i] -=1 
    s = s|1<<C[i] 
  key.append((s,a)) 

INF = float("inf")  
dp = [INF for _ in range(1<<N)]
dp[0] = 0

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

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

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



dp = [ [10**9]*(2**n) for _ in range(m+1) ]
dp[0][0] = 0
for i in range(m):
    a,b = map(int, input().split())
    cl = list(map(int, input().split()))
    cbit = 0
    for c in cl:
        cbit += 2**(c-1)
    
    for j in range(2**n):
        if dp[i][j] == 10**9:
            continue
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][j|cbit] = min(dp[i][j]+a, dp[i][j|cbit], dp[i+1][j|cbit])

ans = dp[m][2**n-1]
if ans >= 10**9:
    ans = -1

print(ans)

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

INF = float("inf")
dp = [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()))
    key = 0
    for c in C:
        key += 2**(c-1)
    for j in range(len(dp)-1, -1, -1):
        if dp[j] == INF:
            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):
n, m = map(int, input().split())
keys = dict()
min_cost = dict()
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for x in c:
        bit |= 1 << (x - 1)
    if bit in keys and keys[bit] <= a:
        continue
    keys[bit] = a
    min_cost[bit] = a

for i in range(1, 1 << n):
    if not i in min_cost:
        continue 
    for bit, cost in keys.items():
        bit |= i
        if i != bit:
            if bit in min_cost:
                min_cost[bit] = min(min_cost[bit], min_cost[i] + cost)
            else:
                min_cost[bit] = min_cost[i] + cost

if not (1 << n) - 1 in min_cost:
    print(-1)
else:
    print(min_cost[(1 << n) - 1])

Solution (Python):
N,M = map(int,input().split())
keys = []
for _ in range(M):
  a,b = map(int,input().split())

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

  keys.append((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]
    cost = dp[s] + keys[i][1]
    dp[t] = min(dp[t], cost)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

key_lis = []
key_cost = []

for _ in range(M):
	a, b = MAP()
	c = LIST()
	key = 0
	for x in c:
		key += 2**(x-1)
	key_lis.append(key)
	key_cost.append(a)


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

for S in range(1<<N):
	for i, key in enumerate(key_lis):
		dp[S|key] = min(dp[S|key], dp[S]+key_cost[i])

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

Solution (Python):
N,M=map(int,input().split())
keys=[]
dp=[float("inf")]*pow(2,N)
dp[0]=0
for i in range(M):
    a,b=map(int,input().split())
    l=list(map(int,input().split()))
    num=0
    for j in l:
        num=num+pow(2,j-1)
    keys.append([a,num])

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

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

Solution (Python):
def min2(x,y):
    return x if x < y else y

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

large = 1<<20
dp = [large]*(1<<N + 1)
dp[0] = 0
data = []
for i in range(M):
    a, b = map(int, input().split())
    bit = 0
    for c in map(int, input().split()):
        c -= 1
        bit = bit|1<<c
    data.append((a, bit))
for i, x in enumerate(data):
    a, bit = x
    for p in range(1<<N):
        dp[p|bit] = min2(dp[p] + a, dp[p|bit])
print(dp[(1<<N)-1] if dp[(1<<N)-1] != large else -1)

Solution (Python):

N, M = map(int, input().split())
X = []
for i in range(M):
    a, _ = map(int, input().split())
    c = list(map(int, input().split()))
    key = sum(1 << (v - 1) for v in c)
    X.append([key, a])

INF = 10 ** 9 + 7
dp = [[INF] * (2 ** N) for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | X[i][0]] = min(dp[i + 1][j | X[i][0]],
                                     dp[i][j] + X[i][1])

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

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

dp=[float("inf")]*g
dp[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c_l=list(map(int,input().split()))
    f=0
    for c_i in c_l:
        f+=1<<(c_i-1)
    for j in range(g-1, -1, -1):
        dp[j|f]=min(dp[j]+a, dp[j|f])

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

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, M = NMI()
    keys = {}
    for i in range(M):
        a, b = NMI()
        C = NLI()
        case = 0
        for c in C:
            case += 2**(c-1)
        keys[i+1] = (a, case)

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

    for key in range(0, M):
        for case in range(2**N):
            if dp[key][case] == 10**10:
                continue
            next_case = case | keys[key+1][1]
            dp[key+1][next_case] = min(dp[key][case] + keys[key+1][0], dp[key+1][next_case])
            dp[key+1][case] = min(dp[key][case], dp[key+1][case])
    ans = dp[M][2**N-1]
    print(ans if ans < 10**10 else -1)






if __name__ == "__main__":
    main()

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, m = ns()
    d = []
    for _ in range(m):
        ai, bi = ns()
        ci = na()
        d.append([ai, bi, ci])

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

    for ai, bi, ci in d:
        getkey = 0
        for cii in ci:
            cii -= 1
            getkey += 1 << cii

        for i in range(2 ** n):
            dp[i | getkey] = min(dp[i | getkey], dp[i] + ai)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, m = ns()
    d = []
    for _ in range(m):
        ai, bi = ns()
        ci = na()
        d.append([ai, bi, ci])

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

    for ai, bi, ci in d:
        getkey = 0
        for cii in ci:
            cii -= 1
            getkey += 1 << cii

        for i in range(2 ** n):
            dp[i | getkey] = min(dp[i | getkey], dp[i] + ai)

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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    INF = 10**9


    N,M = LMIIS()
    keys = []
    for i in range(M):
        a,b = LMIIS()
        boxes = map(lambda x: int(x)-1, input().split())
        key = 0
        for b in boxes:
            key += 2**b
        keys.append((a,key))
        



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

    for key_cost,key in keys:
        for box,cost in enumerate(dp):
            if cost != INF:
                dp[box|key] = min(dp[box|key], cost+key_cost)
    
    ans = dp[2**N-1]
    print(ans if ans != INF else -1)




    




if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int, input().split())
dp = [0]*(2**n + 1)
for i in range(m):
  a,b = map(int, input().split())
  c = list(map(int, input().split()))
  temp=0
  for i in c:
    temp += 2 ** (i-1)
  for i in range(2**n):
    if i != 0 and dp[i] == 0:
      continue
    t = i | temp
    if dp[t] == 0:
      dp[t] = dp[i] + a
    else:
      dp[t] = min(dp[i] + a, dp[t])

ans = dp[2**n - 1]
if ans == 0:
  print(-1)
else:
  print(ans)

Solution (Python):
def resolve():
    N, M = list(map(int, input().split()))
    costs = []
    openables = []
    for i in range(M):
        a, b = list(map(int, input().split()))
        costs.append(a)
        C = list(map(int, input().split()))
        state = 0
        for c in C:
            state += (1<<(c-1))
        openables.append(state)
    
    dp = [[float("inf") for _ in range(4100)] for __ in range(10**3+100)]
    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])
            opened_boxes = openables[i]
            dp[i+1][j|opened_boxes] = min(dp[i+1][j|opened_boxes], dp[i][j]+costs[i])
    print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] < float("inf") else -1)

if __name__ == "__main__":
    resolve()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = []
    C = []
    for i in range(M):
        a, _ = LI()
        bit = 0
        A.append(a)
        c = LI()
        for ix in c:
            bit = bit | 1 << (ix-1)
        C.append(bit)
    dp = [[inf for _ in range(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 | 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)
        return
    print(ans)
    return

main()

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

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

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

ans = dp[-1]

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

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

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

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

ans = dp[-1][-1]

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

Solution (Python):
n, m = map(int,input().split())
a = [0]
b = [0]
c = [0]*(m+1)
for i in range(1, m+1):
    tab = list(map(int, input().split()))
    a.append(tab.pop(0))
    b.append(tab)
    tc1 = list(map(int, input().split()))
    tc2 = 0
    for j in tc1:
        tc2 |= 1<<(j-1)
    c[i] = tc2
INF = 10**9
dp = [[0] + [INF] * (2**n-1) for i in range(m+1)]
for i in range(1, m+1):
    for j in range(2**n):
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        nj = j | c[i]
        dp[i][nj] = min(dp[i][nj], dp[i-1][nj], dp[i-1][j] + a[i])

print(-1) if dp[m][2**n-1] == INF else print(dp[m][2**n-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()

BEST = [INF for i in range(1<<N)]
for i in range(M):
  c,m = IL()
  l = IL()
  b = 0
  for k in l: 
    b |= 1<<(k-1)
  for t in range(1<<N):
    BEST[t&b] = min(BEST[t&b],c)

@lru_cache(maxsize=None) 
def g(b):
  bits = []
  for i in range(N):
    if (b>>i)&1:
      bits.append(i)
  ret = []
  for k in range(1<<len(bits)):
    a = 0
    for j in range(len(bits)):
      if (k>>j)&1:
        a += 1<<bits[j]
    if count_bit(a)!=0 and count_bit(a)!=len(bits):
      ret.append(a)
  return ret
    
@lru_cache(maxsize=None) 
def f(b):
  if count_bit(b) == 1:
    return BEST[b]
  else: 
    return min(BEST[b],min(f(i)+f(b-i) for i in g(b)))
ans = f((1<<N)-1)
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()

BEST = [INF for i in range(1<<N)]
for i in range(M):
  c,m = IL()
  l = IL()
  b = 0
  for k in l: 
    b |= 1<<(k-1)
  for t in range(1<<N):
    BEST[t&b] = min(BEST[t&b],c)

@lru_cache(maxsize=None) 
def f(b):
  if count_bit(b) == 1:
    return BEST[b]
  else: 
    return min(BEST[b],min(f(b&i)+f(b-(b&i)) if (b&i!=b and b-(b&i)!=b) else INF for i in range(1<<N)))
ans = f((1<<N)-1)
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()

BEST = [INF for i in range(1<<N)]
for i in range(M):
  c,m = IL()
  l = IL()
  b = 0
  for k in l: 
    b |= 1<<(k-1)
  for t in range(1<<N):
    BEST[t&b] = min(BEST[t&b],c)

@lru_cache(maxsize=None) 
def f(b):
  if b == 0:
    return INF
  if count_bit(b) == 1:
    return BEST[b]
  else: 
    return min(BEST[b],min(f(b&i)+f(b-(b&i)) if (b&i!=b and b-(b&i)!=b) else INF for i in range(1<<N)))
ans = f((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(int,input().split()))
    k = 0
    for j in c:
        k += 1 << (j-1)
    kagi.append((a,k))
INF = 10 ** 9
dp = [[INF for i in range(m+1)] for i in range(2**n)]
dp[0] = [0 for i in range(m+1)]
for i in range(2**n):
    for j in range(1,m+1):
        dp[i][j] = min(dp[i][j],dp[i][j-1])
        t = i | kagi[j-1][1]
        dp[t][j] = min(dp[t][j],dp[i][j]+kagi[j-1][0])
print(dp[2**n-1][m] if dp[2**n-1][m] != INF else -1)