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())
BIT = 2 ** N
dp =[[float("inf") for _ in range(BIT)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    x = sum([2 ** (c - 1) for c in C])
    for j in range(BIT):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][x|j] = min(dp[i][j] + A, dp[i + 1][x|j])

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

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

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

for i in range(M):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    x = sum([2 ** (c - 1) for c in C])
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][x|j] = min(dp[i][j] + A, dp[i + 1][x|j])

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

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

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

for i in range(M):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    tmp = [0 for _ in range(N)]
    for c in C:
        tmp[c - 1] = 1
    x = int("".join(map(str, tmp)), 2)
    for j in range(2 ** N):
        dp[i + 1][x|j] = min(dp[i][x|j], dp[i][j] + A, dp[i + 1][x|j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

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

Solution (Python):

n, m = map(int, input().split())
ab = []
c= []
keys = ["" for _ in range(m)]

for i in range(m):
    ab.append(list(map(int, input().split())))
    kari = list(map(int, input().split()))
    c.append(kari)
    for j in range(n):
        if j+1 in kari:
            keys[i] = keys[i]+"1"
        else:
            keys[i] = keys[i] + "0"

all_patterns = ["0","1"]
options = ["0", "1"]

for _ in range(n-1):
    all_patterns = [j+i for i in (options) for j in all_patterns]

dp = [1e+10 for i in range(2**n)]
dp[0] = 0


for j in range(m):
    for i in range(len(dp)):
        kari1 = dp[i]+ab[j][0]
        kari2 = dp[i|int(keys[j],2)]
        if kari1 < kari2:
            dp[i|int(keys[j],2)] = kari1

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
lis = []
for i in range(m):
    tmp = list(map(int,input().split()))
    tmp.extend(list(map(int,input().split())))
    lis.append(tmp)

dp = [[1000000000 for i in range(2**n)]for i in range(m+1)]
dp[0][0]=0
for i in range(m):
    clis = 0
    for j in lis[i][2:]:
        clis += 2**(j-1)

    for sin in range(2**n):
        
        dp[i+1][clis|sin] = min(dp[i][sin]+lis[i][0],dp[i+1][clis|sin])
    for sin in range(2**n):
        dp[i+1][sin] = min(dp[i+1][sin],dp[i][sin])



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

Solution (Python):
N,M=map(int,input().split())
key=[[] for _ in range(M)]
for i in range(M):
  A,B=map(int,input().split())
  key[i].append(A)
  C=list(map(int,input().split()))
  bit=0
  for c in C:
    bit+=2**(c-1)
  key[i].append(bit)

dp=[float("inf")]*(2**N)
dp[0]=0
ndp=[0]*(2**N)
for i in range(M):
  cost=key[i][0]
  bit=key[i][1]
  ndp=dp[:]
  for j in range(2**N):
  	ndp[bit|j]=min(dp[j]+cost,ndp[bit|j])
  dp=ndp[:]
 
print(dp[-1] if dp[-1]!=float("inf") else -1)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    dp = [[10**10 for _ in range(2**n)] for _ in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()

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

for i in range(m):
    a,b =  list(map(int,input().split()))
    X =  list(map(int,input().split()))
    bit = 0
    for x in X:
        bit |= 2**(x-1)
    kagi[i] = [a,bit]

ok = 2**n-1
kagi.sort(key=lambda x: x[1])
zenkai = 2**n
dp = [float('inf')]*int(zenkai+1)
dp[0] = 0
for i in range(2**n):
    if dp[i] == float('inf'):
        continue
    for j in range(m):
        s = i|kagi[j][1]
        
        dp[s] = min(dp[s],dp[i] + kagi[j][0])

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

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = []
Cs = []
for i in range(M):
	a, b = rl()
	C = rl()
	A.append(a)
	Cs.append(C)

def get_bit(C):
	b = 0
	for c in C:
		b = b | (1 << (c-1))
	return b
bits =[]
for C in Cs:
	b = get_bit(C)
	bits.append(b)

start = 0
end = 2**N-1

import heapq

heap = []
heapq.heappush(heap, (0, start))

visited = {}
ans = -1
while heap:
	c, n = heapq.heappop(heap)
	if n == end:
		ans = c
		break
	for i, b in enumerate(bits):
		m = n | b
		nc = c + A[i]
		if m in visited and nc >= visited[m]:
			continue
		visited[m] = nc
		heapq.heappush(heap, (nc, m))
print(ans)

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

def solve():
    INF = 10**10

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

    dp = [INF] * (1<<N)
    dp[0] = 0
    for key, cost in zip(keys, costs):
        for S in reversed(range(1<<N)):
            S2 = S | key
            c2 = dp[S] + cost
            if c2 < dp[S2]:
                dp[S2] = c2

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


solve()

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = []
Cs = []
for i in range(M):
	a, b = rl()
	C = rl()
	A.append(a)
	Cs.append(C)

def get_bit(C):
	b = 0
	for c in C:
		b = b | (1 << (c-1))
	return b
bits =[]
for C in Cs:
	b = get_bit(C)
	bits.append(b)

start = 0
end = 2**N-1

import heapq

heap = []
heapq.heappush(heap, (0, start))

visited = {}
ans = -1
while heap:
	c, n = heapq.heappop(heap)
	if n in visited:
		continue
	if n == end:
		ans = c
		break
	visited[n] = 1
	for i, b in enumerate(bits):
		m = n | b
		if m in visited:
			continue
		cost = A[i]
		heapq.heappush(heap, (c + cost, m))
print(ans)

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

def solve():
    INF = 10**10

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

    dp = [INF] * (1<<N)
    dp[0] = 0
    for S in range(1<<N):
        for key, cost in zip(keys, costs):
            S2 = S | key
            c2 = dp[S] + cost
            if c2 < dp[S2]:
                dp[S2] = c2

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


solve()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))

    a = [0] * m
    c = [0] * m

    for i in range(m):
        a[i], _ = list(map(int, readline().split()))
        t = list(map(int, readline().split()))
        for x in t:
            c[i] += (1 << (x - 1))

    dp = [[INF] * (1 << n) for _ in range(m)]
    dp[0][c[0]] = a[0]

    for i in range(m):
        dp[i][0] = 0

    for i in range(1, m):
        key = c[i]
        price = a[i]
        for j in range(1 << n):
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            if dp[i - 1][j] != INF:
                dp[i][j | key] = min(dp[i][j | key], dp[i - 1][j] + price)

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


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
ac = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    ac.append((ai, sum(ci)))

INF = 100 ** 18
dp = [INF] * (2**n)
dp[0] = 0
for ai, ci in ac:
    for j in range(0, 2**n):
        dp[j | ci] = min(dp[j | ci], dp[j] + ai)

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

Solution (Python):
n, m = map(int, input().split())
c = []
a = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    a.append(ai)
    c.append(sum(ci))

INF = 100 ** 18
dp = [INF] * (2**n)
dp[0] = 0
for i in range(m):
    for j in range(0, 2**n):
        dp[j | c[i]] = min(dp[j | c[i]], dp[j] + a[i])

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

Solution (Python):
n, m = map(int, input().split())
c = []
a = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    a.append(ai)
    c.append(sum(ci))

INF = 100 ** 18
dp = [INF] * (2**n + 1)
dp[0] = 0
for i in range(m):
    for j in range(0, 2**n):
        dp[j | c[i]] = min(dp[j | c[i]], dp[j] + a[i])

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

Solution (Python):
n,m=map(int,input().split())
dp=[float("inf")]*(1<<n)
b=[True]*(1<<n)
p=[]
k=0
for i in range(m):
    k=0
    a,_=map(int,input().split())
    c=list(map(int,input().split()))
    for cc in c:
        k+=1<<(cc-1)
    if b[k]:
        b[k]=False
    dp[k]=min(dp[k],a)
    p.append(k)
while True:
    d=[]
    for i in p:
        for j in p:
            if dp[i|j]>dp[i]+dp[j]:
                dp[i|j]=dp[i]+dp[j]
                if b[i|j]:
                    b[i|j]=False
                    d.append(i|j)
    if len(d)==0:
        break
    for oo in d:
        p.append(oo)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**8
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    key = [0]
    box = [0]
    for _ in range(M):
        k,_ = LI()
        key.append(k)
        b = 0
        for c in LI():
            b += 2**(c-1)
        box.append(b)

    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):
            dp[i][j] = min(dp[i-1][j],dp[i-1][j - (j&box[i])]+key[i])
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])
if __name__ == '__main__':
    main()

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

n,m = map(int,readline().split())
c = set()
v = {}
for i in range(m):
  a,b = map(int,readline().split())
  d = list(map(int,readline().split()))
  e = 0
  for j in d:
    e += 2**(j-1)
  if i >= 1:
    s = list(c)
    for k in s:
      if not k|e in c:
        c.add(k|e)
        v[k|e] = a+v[k]
      else:
        v[k|e] = min(v[k|e],a+v[k])
  if not e in c:
    c.add(e)
    v[e] = a
  else:
    v[e] = min(v[e],a)
    
if 2**n-1 in c:
  print(v[2**n-1])
else:
  print(-1)

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

n,m = map(int,readline().split())
c = set()
v = {}
for i in range(m):
  a,b = map(int,readline().split())
  d = list(map(int,readline().split()))
  e = 0
  for j in d:
    e += 2**(j-1)
  if i >= 1:
    s = list(c)
    for k in s:
      if not k|e in c:
        c.add(k|e)
        v[k|e] = a+v[k]
      else:
        v[k|e] = min(v[k|e],a+v[k])
  if not e in c:
    c.add(e)
    v[e] = a
  else:
    v[e] = min(v[e],a)
    
if 2**n-1 in c:
  print(v[2**n-1])
else:
  print(-1)

Solution (Python):
import sys
from collections import defaultdict


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


MOD = 10 ** 9 + 7
sys.setrecursionlimit(20000000)
INF = float("inf")


def main():
    N, M = map(int, input().split())
    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        C = list(map(lambda x: int(x) - 1, input().split()))
        state = 0
        for c in C:
            state += 2 ** c
        key.append((a, state))
    dp = [INF for _ in range(2 ** N)]
    dp[0] = 0
    for i in range(2 ** N - 1):
        for k in range(M):
            state = key[k][1]
            tmp = dp[i] + key[k][0]
            if dp[i | state] > tmp:
                dp[i | state] = tmp
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

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

    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        C = tuple(map(lambda x: int(x) - 1, input().split()))
        status = 0
        for c in C:
            status += 2 ** c
        key.append((a, status))

    for a, status in key:
        if dp[status] > a:
            dp[status] = a

    for i in range(2 ** N - 1):
        for a, status in key:
            new_status = status | i
            if dp[new_status] > dp[i] + a:
                dp[new_status] = dp[i] + a

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    L = pow(2, N)
    Inf = pow(10, 20)
    Dist = [Inf] * L
    
    Dist[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        bit = 0
        C = [int(c) for c in input().split()]
        for c in C: bit += pow(2, c-1)
        for k, d in enumerate(Dist):
            if d < Inf: Dist[k | bit] = min(Dist[k | bit], d + a)
            
    print(Dist[L - 1] if Dist[L-1] < Inf else -1)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))
N, M = inpl()
A = [0]*M
B = [0]*M
C = [0]*M
for m in range(M):
    A[m], B[m] = inpl()
    c = 0
    for x in inpl():
        c += pow(2, x-1)
    C[m] = c
DP = [10**9]*pow(2, N)
DP[0] = 0
for i in range(pow(2, N)):
    if DP[i] > 10**8:
        continue
    for m in range(M):
        DP[i|C[m]] = min(DP[i|C[m]], DP[i] + A[m])
print(DP[-1] if DP[-1] < 10**9 else -1)

Solution (Python):
N, M = map(int, input().split())
A = []
min_state = [10**9] * (2**N)
min_state[0] = 0
for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key = 0
    for tmp in c:
        key += 2**(tmp-1)
    A.append((a, key))
L = len(min_state)
for a, key in A:
    for i, score in enumerate(min_state):
        next_key = key | i

        if min_state[next_key] > score + a:
            min_state[next_key] = score + a
if min_state[-1] == 10**9:
    print(-1)
else:
    print(min_state[-1])

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

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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    L = pow(2, N)
    Dist = [10 ** 20] * L
    
    Dist[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        bit = 0
        C = [int(c) for c in input().split()]
        for c in C: bit += pow(2, c-1)
        for k in range(L):
            if Dist[k] < 10 ** 20: Dist[k | bit] = min(Dist[k | bit], Dist[k] + a)
    if Dist[L - 1] == 10 ** 20: print(-1)
    else: print(Dist[L - 1])



    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    a=[0]*m
    b=[0]*m
    c=[0]*m
    for i in range(m):
        a[i],b[i]=map(int,readline().split())
        li=list(map(int,readline().split()))
        for j in range(len(li)):
            c[i]|=1<<(li[j]-1)

    inf=10**9
    dp=[[inf]*(1<<n) for _ in range(m+1)]
    dp[0][0]=0
    for i in range(1,m+1):
        for j in range(1<<n):
            
            dp[i][j]=min(dp[i-1][j],dp[i][j])

            
            dp[i][j|c[i-1]]=min(dp[i][j|c[i-1]],dp[i-1][j]+a[i-1])

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

if __name__=="__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
up=float('inf')
dp=[[up]*(1<<n) for i in range(m)]
dp[0][0]=0
buy=[]
a=[]
for cnt in range(m):
    x,y=map(int,input().split())
    a.append(x)
    c=list(map(int,input().split()))
    tmp=0
    for w in c:
        tmp|=1<<(w-1)
    buy.append(tmp)
for i in range(m-1):
    for j in range(1<<n):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|buy[i]]=min(dp[i][j]+a[i],dp[i+1][j|buy[i]]) 
if dp[m-1][-1]==float('inf'):
    print(-1)
else:
    print(dp[m-1][-1])

Solution (Python):
n,m=map(int,input().split())
up=float('inf')
dp=[[up]*(1<<n) for i in range(m)]

dp[0][0]=0
buy=[]
a=[]
b=[]
for cnt in range(m):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    c=list(map(int,input().split()))
    tmp=0
    for w in c:
        tmp+=1<<(w-1)
    buy.append(tmp)

for i in range(m-1):
    for j in range(1<<n):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|buy[i]]=min(dp[i][j]+a[i],dp[i+1][j|buy[i]]) 

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

Solution (Python):
n,m=map(int,input().split())
up=float('inf')
dp=[[up]*(1<<n) for i in range(m)]

dp[0][0]=0
buy=[]
a=[]
b=[]
for cnt in range(m):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    c=list(map(int,input().split()))
    tmp=0
    for w in c:
        tmp+=1<<(w-1)
    buy.append(tmp)

for i in range(m-1):
    for j in range(1<<n):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|buy[i]]=min(dp[i][j]+a[i],dp[i+1][j|buy[i]])

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

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

a,c=[],[]
for i in range(M):
    A,B=map(int,input().split())  
    C=list(map(int,input().split()))
    tmp=0
    for j in range(B):
      tmp+=1<<(C[j]-1)
    a.append(A)
    c.append(tmp)
    
dp=[[INF]*(1<<N) for i 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])
        o=(j | c[i])
        dp[i+1][o]=min(dp[i+1][o],dp[i][j]+a[i])
ans=dp[M][2**N-1]
print(ans if ans!=INF else -1)

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

a,c=[],[]
for i in range(M):
    A,B=map(int,input().split())  
    C=list(map(int,input().split()))
    tmp=0
    for j in range(B):
      tmp+=1<<(C[j]-1)
    a.append(A)
    c.append(tmp)
    
dp=[[INF]*(1<<N) for i 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])
        o=(j | c[i])
        dp[i+1][o]=min(dp[i+1][o],dp[i][j]+a[i])
ans=dp[M][2**N-1]
print(ans if ans!=INF else -1)

Solution (Python):
INF = 10**9

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

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

Solution (Python):


getarr = lambda _f: list(map(_f, input().split()))
inf = 10**8 + 1

N, M = getarr(int)

keys = []
key_max = 2**N - 1
for _ in range(M):
    a, b = getarr(int)
    c = getarr(int)
    k = key_max
    for ci in c:
        k -= (1 << (ci - 1))
    keys.append([a, k])
dp = [[inf] * (M + 1) for _ in range(2**N + 1)]
for i in range(M + 1):
    dp[0][i] = 0

for j in range(M):
    for i in range(2**N + 1):
        _cost = keys[j][0]
        _key = keys[j][1]
        dp[i][j + 1] = min(_cost + dp[i & _key][j], dp[i][j])

ans = dp[key_max][M]

print(ans if ans != inf else -1)

Solution (Python):


import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

def tobit(N):
    ret = 0
    for n in N:
        ret |= (1 << n)
    
    return ret

N, M = LI()
C = []
for i in range(M):
    a, b = LI()
    C.append([a, tobit([x-1 for x in LI()])])

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

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

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

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, M = map(int, input().split())
    
    key_price = [0]*M
    key_bit = [0]*M
    for i in range(M):
        key_price[i], b = map(int, input().split())
        c = list(map(int, input().split()))
        for j in range(b):
            key_bit[i] = key_bit[i] | (1 << (c[j] - 1))
    
    dp = [[INF] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0
    for m in range(M):
        for bit in range(2**N):
            if dp[m][bit] == INF:
                continue
            dp[m+1][bit] = min(dp[m+1][bit], dp[m][bit])
            dp[m+1][bit | key_bit[m]] = min(dp[m+1][bit | key_bit[m]], dp[m][bit] + key_price[m])

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    for c in [int(i) for i in input().split()]:
        C[i] |= 1 << (c - 1)

dp = [[float("inf")] * 2 ** N for _ in range(2)]
dp[0][0] = 0
for i, c in enumerate(C):
    for bit in range(2 ** N):
        dp[1][bit] = min(dp[1][bit], dp[0][bit])
        dp[1][c | bit] = min(dp[0][bit] + A[i], dp[1][c | bit])
    dp[0], dp[1] = dp[1], dp[0]
print(dp[0][-1] if dp[0][-1] < float("inf") else - 1)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    for c in [int(i) for i in input().split()]:
        C[i] |= 1 << (c - 1)

dp = [[float("inf")] * 2 ** N for _ in range(2)]
dp[0][0] = 0
for i, c in enumerate(C):
    for bit in range(2 ** N):
        if c & bit == bit:
            dp[1][bit] = min(dp[1][bit], dp[0][bit], A[i])
        else:
            dp[1][bit] = min(dp[1][bit], dp[0][bit])
        dp[1][c | bit] = min(dp[0][c | bit], dp[0][bit] + A[i], dp[1][c | bit])
    dp[0], dp[1] = dp[1], dp[0]
print(dp[0][-1] if dp[0][-1] < float("inf") else - 1)

Solution (Python):
n, m = map(int, input().split())
l = pow(2, n)
inf = pow(10, 7)
pow2 = [pow(2, i) for i in range(n)]
dp = [[inf] * l for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for j in c:
        bit += pow2[j - 1]
    for j in range(l):
        k = j | bit
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        dp[i][k] = min(dp[i][k], dp[i - 1][j] + a)
print(dp[m][l - 1] if not dp[m][l - 1] == inf else -1)

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


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    
    n_states = 1 << N
    end_state = n_states - 1
    dp = [[INF for j in range(2)] for state in range(n_states)]
    dp[0][0] = 0
    dp[0][1] = 0

    for j in range(M):
        m0 = j & 1
        m1 = 1 - m0
        for state in range(n_states):
            next_state = state | C[j]
            dp[state][m1] = min(dp[state][m1], dp[state][m0])
            if next_state > state:
                dp[next_state][m1] = min(dp[next_state][m1], dp[state][m0] + A[j])
    
    m0 = M & 1
    return dp[end_state][m0] if dp[end_state][m0] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

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

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

Solution (Python):
N, M = map(int, input().split())
key = []
for _ in range(M):
  a, b = map(int, input().split())
  s = 0
  C = list(map(lambda x:int(x)-1, input().split()))
  for c in C:
    s |= 1<<c
  key += [(s, a)]
  
dp = [float('inf')]*(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)
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, 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 ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
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 print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False



def main():
    N, M = MI()
    a = [0] * M
    b = [0] * M
    c = [0] * M
    dp = [IINF for i in range(2 ** N)]

    for i in range(M):
        a[i], b[i] = MI()
        tmp = LI()
        for v in tmp:
            c[i] |= 1 << (v-1)

    dp[0] = 0
    for i in range(M):
        for bit in range(2 ** N):
            dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + a[i])

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


if __name__ == '__main__':
    main()

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

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    key = []
    for _ in range(M):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        can_open = 0
        for i in c:
            can_open ^= 1<<(i - 1)
        key.append((a,can_open))
    
    dp = [[INF] * (1<<N) for _ in range(M + 1)]
    for i in range(M):
        dp[i][0] = 0
    
    for i in range(M):
        price,can_open = key[i]
        for s in range(1,1<<N):
            dp[i + 1][s] = min(dp[i][s],dp[i][(s&can_open)^s] + price)
    print(dp[-1][-1] if dp[-1][-1] != INF else -1)

if __name__ == '__main__':
    main()