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())
    maxval = 10 ** (5 + 3 + 2)
    dp = [maxval] * (2 ** N)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        clist = list(map(int,input().split()))
        for ci in clist:
            c |= 1 << (ci - 1)

        newopen = set()
        for op in opened:
            check = op | c
            chkval = dp[op] + a
            if dp[check] > chkval:
                dp[check] = chkval
                newopen.add(check)
            newopen.add(c)

        opened = opened | newopen
        
    ans = dp[-1]
    if ans == maxval:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N,M=list(map(int,input().strip().split(" ")))
keys=[]
want=2**N-1
for _ in range(M):
    a,b=list(map(int,input().strip().split(" ")))
    c=list(map(int,input().strip().split(" ")))
    temp=0
    for i in c:
        temp+=2**(i-1)
    keys+=[(a,temp)]

dp=[float("inf")]*(2**N)
dp[0]=0
for i in range(len(dp)):
    for j in range(len(keys)):
        price,val=keys[j]
        if i&val==0:
            continue
        dp[i]=min(dp[i-(i&val)]+price,dp[i])
        
        


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

Solution (Python):
import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

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

Solution (Python):

n, m = map(int, input().split())
INF = 1001001001
key_list = []
cost_list = []
for i in range(m):
  a, b = map(int, input().split())
  cost_list.append(a)
  c = list(map(int, input().split()))
  s = 0
  for j in range(b):
    s |= 1 << c[j] - 1
  key_list.append(s)
   
dp = [INF] * (1 << n)
dp[0] = 0
for s in range(1 << n):
  for i in range(m):
    t = s | key_list[i]
    cost = dp[s] + cost_list[i]
    dp[t] = min(cost, dp[t])
if dp[-1] == INF:
  ans = -1
else:
  ans = dp[-1]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from pprint import pprint
N, M = map(int, input().split())
A = [-1]*M
B = [-1]*M
C = [-1]*M

for i in range(M):
    A[i], B[i] = map(int, input().split())
    ls = list(map(int, input().split()))
    c = 0
    for j in range(len(ls)):
        c += 2 ** (ls[j]-1)
    C[i] = c


dp = [[float('inf')]*(2**N) for _ in range(M)]

j = 0
for i, di in enumerate(C):
    if i == 0:
        dp[i][di] = A[i]
        dp[i][0] = 0
        continue
    for j in range(2**N):
        stay = dp[i - 1][j | di]
        buy = dp[i - 1][j] + A[i]
        now = dp[i][j | di]
        dp[i][j | di] = min(stay, buy, now)
    for j in range(2**N):
        dp[i][j] = min(dp[i][j], dp[i-1][j])

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    cur = i % 2
    nxt = (i+1) % 2
    
    dp[nxt] = dp[cur][:]
    for j in range(1<<N):
        if dp[cur][j] != INF:
            m = j | s
            
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
ans = dp[M%2][-1]

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

Solution (Python):
N, M = [int(v) for v in input().split(' ')]

a_array = []
b_array = []
c_array = []


for i in range(M):
    a, b = [int(v) for v in input().split(' ')]
    bit = 0
    for c in input().split(' '):
        bit |= 1 << (int(c) - 1)

    a_array.append(a)
    b_array.append(b)
    c_array.append(bit)

key = 0
for c in range(N):
    key |= (1 << c)

dp = [-1 for i in range(key+1)]
dp[0] = 0

for item in range(0, M):
    now = c_array[item]

    for bits in range(0, 1 << N):
        cost1 = dp[bits]
        if cost1 < 0:
            continue

        cost1 += a_array[item]
        cost = dp[bits | now]
        if cost < 0 or cost > cost1:
            dp[bits | now] = cost1
    
print(dp[key])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    cur = i % 2
    nxt = (i+1) % 2
    
    dp[nxt] = dp[cur][:]
    for j in range(1<<N):
        if dp[cur][j] != INF:
            m = j | s
            
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
ans = dp[M%2][-1]

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
cur = 0
nxt = 1
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        
        dp[nxt][j] = min(dp[nxt][j], dp[cur][j])
        if dp[cur][j] != INF:
            m = j | s
            
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
    cur, nxt = nxt, cur
ans = dp[M%2][-1]

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    cur = i % 2
    nxt = (i+1) % 2
    for j in range(1<<N):
        
        dp[nxt][j] = min(dp[nxt][j], dp[cur][j])
        if dp[cur][j] != INF:
            m = j | s
            
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
ans = dp[M%2][-1]

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        
        dp[(i+1)%2][j] = min(dp[(i+1)%2][j], dp[i%2][j])
        if dp[i%2][j] != INF:
            m = j | s
            
            dp[(i+1)%2][m] = min(dp[(i+1)%2][m], dp[i%2][j]+c)
ans = dp[M%2][-1]

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(M+1, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i][j] != INF:
            m = j | s
            
            dp[i+1][m] = min(dp[i+1][m], dp[i][j]+c)
ans = dp[M][-1]

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

Solution (Python):
INF = 10 ** 9 + 1

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

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

dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for state, val in key:
        t = s | state
        cost = dp[s] + val
        dp[t] = min(dp[t], cost)


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

Solution (Python):
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        key = []
        for _ in range(M):
            a, b = map(int, input().split())
            s = 0
            for box_num in map(int, input().split()):
                s |= 1 << (box_num - 1)
            key.append([a, s])

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

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



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()


keys = [None] * M
for i in range(M):
    c, _ = MAP()
    
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)


dp = list2d(M+1, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<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]+c)
ans = dp[M][-1]

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

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

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

S = []

for m in range(M):
    A, B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    s = 0
    for c in C:
        s |= 1 << (c-1)
    S.append((s, A))

DP = [float("inf")] * (1 << N)
DP[0] = 0

for i in range(1 << N):
    for s, a in S:
        t = i | s
        DP[t] = min(DP[t], DP[i] + a)

if DP[-1] == float("inf"):
    print(-1)
    sys.exit(0)

print(DP[-1])

Solution (Python):


def main():
    N, M = map(int, input().split())
    inf = int(1e10)
    
    dp = [inf] * (2**N) 
    
    
    
    dp[0] = 0
    bits = set()
    bits.add(0)
    
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        
        key = 0
        for t in c:
            key += 1 << (t - 1)
        
        
        
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            
            
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        
        

        bits = add_bits|bits
        
    
    if dp[(1 << N) - 1] == inf:
        print(-1)
    else:
        print(dp[(1 << N) - 1])
    

if __name__ == "__main__":
    main()

Solution (Python):
n, m= list(map(int, input().split()))
key=[]
for i in range(m):
    a,b= list(map(int, input().split()))
    c= list(map(int, input().split()))
    s=0
    for j in range(b):
        s|=1<<c[j]-1
    tmp=[s,a]
    key.append(tmp)
inf=1001001001
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]
        cost=dp[s]+key[i][1]
        dp[t]=min(dp[t],cost)
ans=dp[-1]
if ans==inf:
    ans=-1
print(ans)

Solution (Python):


import array
import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


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


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


INF = 2 ** 31 - 1


def solve(N, M, A, B, C):
    D = []
    for c in C:
        b = 0
        for v in c:
            b |= 1 << (v - 1)
        D.append(b)

    bits = 1 << N
    dp = array.array('i', [INF] * bits)

    dp[0] = 0
    for a, d in zip(A, D):
        for b in range(bits):
            if dp[b] == INF:
                continue
            nb = b | d
            dp[nb] = min(dp[nb], dp[b] + a)

    if dp[bits - 1] == INF:
        return -1
    return dp[bits - 1]


def main():
    N, M = [int(e) for e in inp().split()]
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = [int(e) for e in inp().split()]
        c = [int(e) for e in inp().split()]
        A.append(a)
        B.append(b)
        C.append(c)
    print(solve(N, M, A, B, C))


if __name__ == '__main__':
    main()

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

dp = [10**6 for i in range(2**n)]
dp[0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[j|di] = min(dp[j|di], dp[j]+a[i])

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

Solution (Python):
N,M=map(int,input().split())
r=[0]+[10**9]*(2**N-1)
for i in range(M):
    a,_=map(int,input().split())
    c=map(int,input().split())
    x=0
    for e in c:
        x+=1<<(e-1)
    for j in range(2**N):
        r[x|j]=min(r[x|j],r[j]+a)
print(r[-1] if r[-1]<10**9 else -1)

Solution (Python):
if __name__ == "__main__":
    N, M = map(int, input().split())
    key_data = list()
    INF = 1001001001
    for i in range(M):
        a, b = map(int, input().split())
        c = sum(1 << (ci - 1) for ci in map(int, input().split()))
        key_data.append([a, c])

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

    for j in range(2**N):
        for i in range(M):
            k = j | key_data[i][1]
            cost = dp[j] + key_data[i][0]
            if dp[k] > cost:
                dp[k] = cost

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

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

keys = [None] * m
dlen = 2**n
inf = float("inf")
dp = [inf] * dlen

for i in range(m):
    a, _ = map(int, input().split())
    c = 0
    for num in map(int, input().split()):
        c += 2 ** (num - 1)
    
    keys[i] = (a, c)

for price, key in keys:
    for i in range(dlen):
        if dp[i] == inf: continue
        new = key | i
        dp[new] = min(dp[new], dp[i] + price)
    
    dp[key] = min(dp[key], price)

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

Solution (Python):
if __name__ == "__main__":
    N, M = map(int, input().split())
    key_data = list()
    INF = 1001001001
    for i in range(M):
        a, b = map(int, input().split())
        c = sum(1 << (ci - 1) for ci in map(int, input().split()))
        key_data.append([a, c])

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

    for j in range(2**N):
        for i in range(M):
            k = j | key_data[i][1]
            cost = dp[j] + key_data[i][0]
            if dp[k] > cost:
                dp[k] = cost

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

Solution (Python):


Input1 = [input() for i in range(1)]
N,M = list(map(int,Input1[0].split()))
Input2 = [input() for i in range(M*2)]
A,B,C = [],[],[]
for i in range(M):
    a,b = list(map(int,Input2[i*2].split()))
    A.append(a)
    B.append(b)
    c = list(map(int,Input2[i*2+1].split()))
    C.append(c)

d = []
for c in C:
    r = 0
    for j in c:
        r |= 2**(j-1)
    d.append(r)

dp = [1000000000]*2**N
dp[0] = 0
for i in range(2**N): 
    for j in range(M): 
        temp = d[j] | i 
        cost = dp[i] + A[j]
        if dp[temp] > cost: 
            dp[temp] = cost 

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

Solution (Python):
N,M = map(int,input().split())
INF = 10**8
N_dp = 2**N
DP = [INF] * (N_dp)
DP[0] = 0

for i in range(M):
    a,b = map(int,input().split())
    C = [int(i) for i in input().split()]
    c_bit = sum(2**(c-1) for c in C)
    for i in range(N_dp):
        DP[c_bit | i] = DP[i] + a if(DP[i]+a < DP[c_bit | i]) else DP[c_bit | i]
if(DP[-1] == INF):
    DP[-1] = -1
print(DP[-1])

Solution (Python):

 
N,M = map(int,input().split())
 
lis = [float("inf")] * (2 ** N)
lis[0] = 0
 
for i in range(M):
 
    a,b = map(int,input().split())
 
    c = list(map(int,input().split()))
 
    num = 0
    for j in c:
        num += 2 ** (j-1)
 
    nlis = lis.copy()
    for j in range(2 ** N):
 
        if lis[j | num] > nlis[j] + a:
            lis[j | num] = nlis[j] + a     
 

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

Solution (Python):


 
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))
    value.append([A, c])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        if dp[t] > cost:
            dp[t] = cost
        
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])

Solution (Python):

import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  
    B[i] = b  
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
    
dp = [INF]*(1<<N) 
dp[0] = 0 

for s in range(1<<N): 
    for j in range(M): 
        t = s | C[j] 
                     
                     
        cost = dp[s] + A[j] 
        dp[t] = min(dp[t],cost) 
ans = dp[-1] 
if ans == INF: 
               
    ans = -1
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string


import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7

sys.setrecursionlimit(10**6)

show_flg=False


n,m=MI()
t=1<<n
key=[]
for i in range(m):
    a,b=MI()
    c=0
    for j in LI_():
        c+=1<<j
    key.append((a,c))
inf=float('inf')
dp=[[inf]*(m+1) for _ in range(t)]

dp[0][0]=0

for j in range(1,m+1):
    for i in range(t):
        cost,ck=key[j-1]
        show(i,j,'|',dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        dp[ck|i][j]=min(dp[ck|i][j],dp[ck|i][j-1],dp[i][j-1]+cost)
        dp[i][j]=min(dp[i][j],dp[i][j-1])
        
for i in dp:
    show(*i)

ans=dp[t-1][m] if dp[t-1][m]!=inf else -1
print(ans)

Solution (Python):

import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  
    B[i] = b  
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
dp = [INF]*(1<<N) 
dp[0] = 0
for s in range(1<<N):
    for j in range(M):
        t = s | C[j]
        cost = dp[s] + A[j]
        dp[t] = min(dp[t],cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

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

Solution (Python):
def main():
    n, m = map(int, input().split())
    k = []
    for i in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<i for i in map(lambda x: int(x)-1, input().split())])
        k.append((a, c))
    dp = [float("inf")]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        for ki in range(m):
            c = dp[i] + k[ki][0]
            t = i | k[ki][1]
            dp[t] = min(dp[t], c)

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

if __name__ == "__main__":
    main()

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



X = [10**8+1]*N2
X[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    
    
    k = sum(1<<(c-1) for c in C)
    for j in range(N2):
        
        if X[j|k] > X[j] + a:
            X[j|k] = X[j] + a

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

Solution (Python):
INF = 1000000000

N, M = list(map(int, input().split()))
a_list = []
c_list = []
for i in range(M):
    a, _ = list(map(int, input().split()))
    a_list.append(a)
    c = 0
    for one in list(map(int, input().split())):
        c |= 1<<(one-1)
    c_list.append(c)

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

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

Solution (Python):
def calc(N, M, a, c):
    for j in range(N):
        u = sum([c[i][j] for i in range(M)])
        if u == 0:
            return -1
    inf = 10 ** 7 + 1
    L = 2 ** N
    dp = [inf for _ in range(L)]
    dp[0] = 0
    C = [sum([_c[i] * 2 ** i for i in range(N)]) for _c in c]
    for _ in range(M):
        dp_x = list(dp)
        for i in range(M):
            for j in range(L):
                if dp[j] == inf:
                    continue
                dp_x[j | C[i]] = min(dp_x[j | C[i]], dp[j] + a[i])
            dp = dp_x
        if dp[L - 1] < inf:
            return dp[L - 1]
    return -1


(N, M) = tuple([int(s) for s in input().split(' ')])
a = [0 for _ in range(M)]
c = [[0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    (_a, _b) = tuple([int(s) for s in input().split(' ')])
    a[i] = _a
    for _c in [int(s) for s in input().split(' ')]:
        c[i][_c - 1] = 1
print(calc(N, M, a, c))

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

ab=[]
cs=[]
for i in range(m):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    ab.append((a,b))
    cs.append(c)
dp=[inf]*(2**n)
dp[0]=0
for i in range(m):
    x=0
    for h in cs[i]:
        x+=2**(h-1)
    for j in range(2**n):
        dp[j|x]=min(dp[j|x],dp[j]+ab[i][0])
print(dp[-1] if dp[-1]!=inf else -1)

Solution (Python):
N,M= map(int, input().split())
INF = float("inf")
key = []
for i in range(M):
    a, b = map(int, input().split())
    f = 0
    for c in list(map(int, input().split())):
        c -= 1
        f |= 1 << c
    key.append((f, a))
dp = [INF] * (1 << N) 
dp[0] = 0
 
for f in range(1 << N): 
    for i in range(M):
        t = f | key[i][0]
        cost = dp[f] + key[i][1]
        dp[t] = min(dp[t], cost)

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

Solution (Python):
n, m = map(int, input().split())
dp = [[float('inf')] * 2 ** n for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = [int(i_) for i_ in input().split()]
    temp = 0
    for kk in c:
        temp += 1 << (kk - 1)
    for j in range(2 ** n):
        if j == 0:
            dp[i][temp | j] = a
        else:
            dp[i][temp | j] = min(dp[i - 1][j] + a, dp[i][temp | j])
        if (i > 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j])

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

Solution (Python):
n, m = list(map(int, input().split()))
 
a = []
b = []
c = {}
for i in range(m):
    _a, _b = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c[i] = list(map(int, input().split()))
    
inf = int(10e+6)
 
dp = [inf]*(2**n)
dp[0] = 0
 
def rec(dp_i, cost):
    if dp[dp_i] > cost:
        dp[dp_i] = cost
        
    return
 
for _ci, _cv in c.items():
    now = 0
    for _v in _cv:
        now |= 1 << _v-1
    
    for bits in range(1 << n):
        rec(bits|now, dp[bits] + a[_ci])
 
        
if dp[(1 << n) - 1] == inf:
    print(-1)
else:
    print(dp[(1 << n) - 1])

Solution (Python):

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
A = []
C = []

for i in range(M):
    A.append(int(input().split()[0]))
    C.append(list(map(int,input().split())))


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

for i in range(M):
    cost = A[i]
    candidate = C[i]
    mask = 0
    for c in candidate:
        mask += 1 << (c-1)
    for j in range(2**N):
        if dp[j|mask] > dp[j] + cost:
            dp[j|mask] = dp[j] + cost

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

Solution (Python):

def main():
    N, M = map(int, input().split())
    inf = int(1e10)
    dp = [inf] * (1 << N) 
    
    dp[0] = 0
    bits = set()
    bits.add(0)
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        
        key = 0
        for t in c:
            key += 1 << (t - 1)
        
        
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        bits |= add_bits
    
    if dp[(1 << N) - 1] == inf:
        print(-1)
    else:
        print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()