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):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        def k(s):
            if dp[s|c] > dp[s] + a:
                dp[s|c] = dp[s] + a
        [k(s) for s in range(p)]
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(1,None)]*n
    for x in c:
        l0[x-1] = slice(None,1)
        l1[x-1] = slice(None)
    dp = np.minimum(np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a), dp)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        def k(s):
            dp[s|c] = dp[s] + a
        [k(s) for s in range(p) if dp[s|c] > dp[s] + a]
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        for s in range(p):
                if dp[s|c] > dp[s] + a:
                    dp[s|c] = dp[s] + a
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                new = dp[s] + a
                if dp[t] > new:
                    dp[t] = new
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                new = dp[s] + a
                if dp[t] > new:
                    dp[t] = new
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(1,2)]*n
    for x in c:
        l0[x-1] = slice(0,1)
        l1[x-1] = slice(None)
    dp = np.minimum(np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a), dp)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = float('inf')
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**20
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    dp = [10**7]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == 10**7:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    dp = [10**7]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == 10**7:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)
T = []
for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    T.append(t)


n2 = 2**n

DP = [[float("inf") for i in range(n2)] for j in range(m+1)]
for i in range(m+1):
    DP[i][0] = 0

for i in range(1,m+1):
    t = T[i-1]
    for j in range(n2):
        
        
        DP[i][j|t] = min(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j] = min(DP[i][j], DP[i-1][j])
        

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

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    dp = [float('inf')]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == float('inf'):
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
I=lambda:map(int,input().split());n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a,_=I();s=sum(1<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

Solution (Python):
I=lambda:list(map(int,input().split()));n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a=I()[0];s=sum(1<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

Solution (Python):
n, m = map(int, input().split())
dp = [float('inf')] * 2**n
dp[0] = 0
for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    for s in range(2**n):
            t = s|c
            if dp[t] > dp[s] + a:
                dp[t] = dp[s] + a
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)

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

C = 2 ** n
INF = 10 ** 6

dp = [[INF for _ in range(C)] for __ in range(m + 1)]
for i in range(m+1):
    dp[i][0] = 0

for i, ki in enumerate(k):
    for j in range(C):
        dp[i+1][j] = dp[i][j]
    for j in range(C):
        dp[i+1][j | ki[1]] = min(dp[i+1][j | ki[1]], dp[i][j] + ki[0])

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

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
k = []
for _ in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    k.append((a, sum([2 ** (i-1) for i in c])))

C = 2 ** n
INF = 10 ** 6

dp = [[INF for _ in range(C)] for __ in range(m + 1)]
for i in range(m+1):
    dp[i][0] = 0

for i, ki in enumerate(k):
    for j in range(C):
        dp[i+1][j] = dp[i][j]
    for j in range(C):
        dp[i+1][j | ki[1]] = min(dp[i+1][j | ki[1]], dp[i][j] + ki[0])

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

Solution (Python):
n, m = map(int, input().split())
ac = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    ac.append([a, c])
dp = [float('inf')] * 2**n
dp[0] = 0
for s in range(2**n):
    for a, c in ac:
        t = s|c
        if dp[t] > dp[s] + a:
            dp[t] = dp[s] + a
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)

Solution (Python):

"""
bitDPというらしい
dp[i][j] = i番目の入力に対して、状態jを実現する最小値
j : 2^12通り。それぞれの宝箱をbitと見立てる
"""

N, M = map(int, input().split())
INF = 10**5+1


dp = [INF for i in range(2**N+1)]
dp[0] = 0

for i in range(M):
    cost,b = map(int, input().split())
    boxes = list(map(int, input().split()))
    status = 0
    for box in boxes:
        status += 2**(box-1)
    for j in range(2**N):
        if dp[j] != INF:
            nxt = status | j
            dp[nxt] = min(dp[j] + cost, dp[nxt])

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

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

ab_list = []
c_list = []
for i in range(M):
    ab_list.append(list(map(int,input().split())))
    c_list.append(list(map(int,input().split())))
    
cost = [float("inf")]*(2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in c_list[i]:
        move += 2**(j-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j]
        if cost[i|move2] > cost[i]+ab_list[j][0]:
            cost[i|move2] = cost[i]+ab_list[j][0]

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

Solution (Python):

"""
bitDPというらしい
dp[i][j] = i番目の入力に対して、状態jを実現する最小値
j : 2^12通り。それぞれの宝箱をbitと見立てる
"""

N, M = map(int, input().split())
INF = 10**5+1


dp = [[INF for i in range(2**N+1)] for j in range(1100)]
dp[0][0] = 0

for i in range(M):
    dp[i+1] = [v for v in dp[i]]
    cost,b = map(int, input().split())
    boxes = list(map(int, input().split()))
    status = 0
    for box in boxes:
        status += 2**(box-1)
    for j in range(2**N):
        if dp[i][j] != INF:
            nxt = status | j
            dp[i+1][nxt] = min(dp[i][j] + cost, dp[i][nxt], dp[i+1][nxt])

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

Solution (Python):
INF = 99999999999
n, m = map(int,input().split())
V = []
K = []
for _ in range(m):
    value, _ = map(int,input().split())
    V.append(value)
    tmp = [0] * n
    for i in map(int,input().split()):
        tmp[i-1] = 1
    tmp = int("".join(map(str, tmp)), 2)
    K.append(tmp)
dp = {}
import itertools
for flags in itertools.product([0,1], repeat=n):
    tmp = int("".join(map(str, list(flags))), 2)
    dp[tmp] = INF
for i in range(m):
    k = K[i]
    v = V[i]
    if v < dp[k]:
        dp[k] = v
    for dp_k, dp_v in dp.items():
        _k_sum = dp_k | k
        _v_sum = v + dp_v
        if _v_sum < dp[_k_sum]:
            dp[_k_sum] = _v_sum
_max = max(dp.keys())
if dp[_max] == INF:
    print(-1)
else:
    print(dp[_max])

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

INF = 10**12
N,M = map(int,input().split())
K = []
for i in range(M) :
    a,b = map(int,input().split())
    s = 0 
    cx = list(map(int,input().split()))
    for c in cx :
        s = s | (1 << (c-1)) 
    K.append([s, a])


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

for bit in range(1 << N) :
    for i in range(M) :
        s,a = K[i]
        t = bit | s
        cost = dp[bit] + a
        dp[t] = min(dp[t], cost)
ans = -1 if dp[-1] == INF else dp[-1]

print(ans)

Solution (Python):
import sys


INF = 10**12
N,M = map(int,input().split())
K = []
for i in range(M) :
    a,b = map(int,input().split())
    s = 0 
    cx = list(map(int,input().split()))
    for c in cx :
        s = s | (1 << (c-1)) 
    K.append([s, a])


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

for bit in range(1 << N) :
    for i in range(M) :
        s,a = K[i]
        t = bit | s
        cost = dp[bit] + a
        dp[t] = min(dp[t], cost)
ans = -1 if dp[-1] == INF else dp[-1]

print(ans)

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

    input = sys.stdin.readline

    inf = (10 ** 5) * (10 ** 3)

    n, m = map(int, input().split())
    size = 1 << n

    dp = [inf] * size
    dp[0] = 0

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

        mask = 0
        for k in c:
            mask |= 1 << k

        for b in range(size - 1):
            if dp[b] == inf:
                continue
            nb = b | mask
            dp[nb] = min(dp[nb], dp[b] + cost)

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


if __name__ == '__main__':
    main()

Solution (Python):


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

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

ans = dp[-1] if dp[-1] != 10**12 else -1

print(ans)

Solution (Python):
N,M = map(int,input().split())
dp = [[float("inf")]*(2**N) for i in range(M+1)]
AC = []
ans = 0
for i in range(M):
    ai,bi = map(int,input().split())
    ci = list(map(int,input().split()))
    ci = sum([2**(i-1) for i in ci])
    AC.append([ai,ci])
for i in range(M+1):
    dp[i][0] = 0
for i in range(M):
    for j in range(2**N):
        if dp[i][j] != float("inf"):
            dp[i+1][j|AC[i][1]] = min(dp[i+1][j|AC[i][1]],dp[i][j]+AC[i][0]) 
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

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

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

    input = sys.stdin.readline

    inf = (10 ** 5) * (10 ** 3)

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

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

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

        mask = 0
        for k in c:
            mask |= 1 << k

        for b in range((1 << n) - 1):
            if dp[b] == inf:
                continue
            nb = b | mask
            dp[nb] = min(dp[nb], dp[b] + cost)

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


if __name__ == '__main__':
    main()

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

keys = []

for i in range(m):
    cost, num = map(int, input().split())
    C = list(map(int, input().split()))
    can_open = 0
    for c in C:
        can_open += 2 ** (c-1)
    keys.append([cost, can_open])

DP = {}
for i in range(2**n):
    DP[i] = float('INF')
DP[0] = 0

for cost, can_open in keys:
    for key in DP.keys():
        pre_cost = DP[key]
        next_key = key | can_open
        DP[next_key] = min(DP[next_key], pre_cost+cost)


full_open = (1 << n) - 1

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

Solution (Python):
I=lambda:list(map(int,input().split()));n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a=I()[0];s=sum(2**~-c for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

Solution (Python):

import sys
input = sys.stdin.readline


def main():
    INF = 10**9
    N, M = map(int, input().split())
    h = []
    dp = [INF for i in range(1 << N)]

    for i in range(M):
        a, b = map(int, input().split())
        s = 0
        for c in map(int, input().split()):
            c -= 1
            s |= 1 << c
        h.append((a, s))

    dp[0] = 0

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

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


if __name__ == '__main__':
    main()

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

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

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

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

    mask = 0
    for k in c:
        mask |= 1 << k

    for b in range((1 << n) - 1):
        nb = b | mask
        dp[nb] = min(dp[nb], dp[b] + cost)

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

Solution (Python):
def main():
  I=lambda:list(map(int,input().split()))
  n,m=I()
  e=[(I()[0],[1<<n-i for i in I()])for _ in'_'*m]
  I=9**9
  dp=[I]*2**n
  dp[0]=0
  for i,d in enumerate(dp):
    if d==I:continue
    for a,c in e:
      b,x=i,d+a
      for j in c:b|=j
      if dp[b]>x:dp[b]=x
  print(-(dp[-1]==I)or dp[-1])
main()

Solution (Python):
n, m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*(2**n)
dp[0] = 0
for i in range(m):
    a, b = input().split(' ')
    a = int(a)
    b = int(b)
    M = 0
    for j in input().split(' '):
        M += 2**(int(j)-1)

    for j in range(2**n):
        
        
        if dp[j] + a < dp[j|M]:
            dp[j|M] = dp[j] + a


print(dp[2**n-1] if dp[2**n-1] < float('inf') else -1)

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

def main():
    N, M = map(int, input().split())
    dp = [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 i in c:
            key += 2 ** (i-1)
        for j in range(2**N):
            dp[j|key] = min(dp[j|key], dp[j]+a)
    if dp[2**N-1] == INF:
        print(-1)
    else:
        print(dp[2**N-1])


if __name__ == '__main__': main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    e=[(int(input().split()[0]),[2**(n-i)for i in map(int,input().split())])for _ in range(m)]
    I=9**9
    dp=[I]*2**n
    dp[0]=0
    for i,dpi in enumerate(dp):
        if dpi==I:continue
        for a,c in e:
            b=i
            for j in c:b|=j
            cost=dpi+a
            if dp[b]>cost:dp[b]=cost
    print(-(dp[-1]==I)or dp[-1])
main()

Solution (Python):
n, m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*(2**n)
dp[0] = 0
for i in range(m):
    a, b = input().split(' ')
    a = int(a)
    b = int(b)
    M = 0
    for j in input().split(' '):
        M += 2**(int(j)-1)

    for j in range(2**n):
        
        dp[j|M] = dp[j] + a if dp[j] + a < dp[j|M] else dp[j|M]

    
    
    

print(dp[2**n-1] if dp[2**n-1] < float('inf') else -1)

Solution (Python):
n, m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*(2**n)
dp[0] = 0
for i in range(m):
    a, b = input().split(' ')
    a = int(a)
    b = int(b)
    M = 0
    for j in input().split(' '):
        M += 2**(int(j)-1)

    
    

    for j in range(2**n):
        if dp[j|M] > dp[j] + a:
            dp[j|M] = dp[j] + a

print(dp[2**n-1] if dp[2**n-1] < float('inf') else -1)

Solution (Python):
n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])

Solution (Python):
N, M = map(int, input().split())
ABC = []
for i in range(M):
    ab = list(map(int,input().split()))
    c = list(map(int, input().split()))
    ab.append(c)
    ABC.append(ab)
    
INF = float('inf')
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    d = 0
    for c in ABC[i][2]:
        d |= (1 << (c-1))
        
    for j in range(2**N):
        dp[j|d] = min(dp[j|d], dp[j]+ABC[i][0])
        
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

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

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

for i in range(m):
    a, b = map(int, input().split())
    c_list = list(map(int, input().split()))
    c = 0
    for j in range(b):
        c += 1 << (c_list[j]-1)

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])

if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)

Solution (Python):
import sys

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 main():
    N,M = LI()
    keys = []
    for _ in range(M):
        a,b = LI()
        C = LI_()
        key_bit = 0
        for c in C:
            key_bit += (1 << c)
        keys.append([a,key_bit])

    dp = [10**10] * (1 << N)
    dp[0] = 0
    for i in range(0,M):
        for key_bit in range(1 << N):
            dp[key_bit|keys[i][1]] = min(dp[key_bit|keys[i][1]],dp[key_bit]+keys[i][0])
    if(dp[(1<<N)-1] == 10**10):
        return(-1)
    return(dp[(1<<N)-1])


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

Solution (Python):
import sys

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 main():
    N,M = LI()
    keys = []
    for _ in range(M):
        a,b = LI()
        C = LI_()
        key_bit = 0
        for c in C:
            key_bit += (1 << c)
        keys.append([a,key_bit])

    dp = [[10**10] * (1 << N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(0,M):
        for key_bit in range(1 << N):
            dp[i+1][key_bit] = min(dp[i][key_bit],dp[i+1][key_bit])
            dp[i+1][key_bit|keys[i][1]] = min(dp[i+1][key_bit|keys[i][1]],dp[i][key_bit]+keys[i][0])
    if(dp[M][(1<<N)-1] == 10**10):
        return(-1)
    return(dp[M][(1<<N)-1])


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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def matdprint(mat):
    if debug == True:
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                print(mat[i][j], end=', ')
            print()

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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7
def conv(s):
    cnt = 0
    for n in s:
        cnt += 2**n
    return cnt

def main():

    N, M = LI()

    a_list = []
    b_list = []
    c_list = []
    for i in range(M):
        a, b = LI()
        a_list.append(a)
        
        c_list.append(LI())

    dp = [[0 for j in range(2**N)]for i in range(M)]

    def conv(c):
        key = 0
        for i in c:
            key += 2**(i-1)
        return key

    def update(i, j, a):
        if dp[i][j] == 0:
            dp[i][j] = a
        else:
            dp[i][j] = min(dp[i][j], a)

    for i in range(M):
        c = c_list[i]
        a = a_list[i]
        key = conv(c)
        dprint('i', i, 'a', a, 'key', key)

        
        if dp[i - 1][key] != 0:
            dp[i][key] = min(dp[i - 1][key], a)
        else:
            dp[i][key] = a


        for j in range(2**N):
            org_key = j
            or_key = j | key

            
            
            
            
            
            if dp[i - 1][org_key] != 0:

                
                update(i, or_key, dp[i-1][org_key] + a)

                

            
            if dp[i-1][j] != 0:
                update(i, j, dp[i-1][j])

        

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

main()

Solution (Python):
n, m = list(map(int, input().split()))
dp = [pow(10, 10) for _ in range(pow(2, n))]

dp[0] = 0
for _ in range(m):
    a, b = list(map(int, input().split()))
    cs = list(map(int, input().split()))
    d = 0
    for c in cs:
        d += pow(2, (c-1))
    for i in range(pow(2, n)):
        dp[i|d] = min(dp[i|d], dp[i] + a)

if dp[pow(2,n)-1] == pow(10, 10):
    print(-1)
else:
    print(dp[pow(2,n)-1])

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

INF = float('inf')
dp = [INF for j in range(2**n)]

dp[0] = 0

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

    k = 0
    for ci in c:
        ci -= 1
        k |= (1 << ci)
    for j in range(2**n):
        l = k | j
        dp[l] = min(dp[l], dp[j] + a)

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

Solution (Python):
n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])

Solution (Python):
import sys

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

dp = [INF]*(2**N)
dp[0] = 0
for m in range(M):
    a = costs[m]
    key = keys[m]
    for i in range(2**N):
        
        dp[i|key] = min(dp[i|key], dp[i]+a)
ans = dp[-1]
if ans == INF:
    print(-1)
else:
    
    print(dp[-1])