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



Sample input:
2 3
10 1
1
15 1
2
30 2
1 2


Sample output:
25

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)

Submission status: Accepted

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

key = [0 for i in range(M)]
cost = []

for i in range(M):
    a,b = list(map(int,input().split()))
    c = list(map(int,input().split()))
    cost.append(a)
    for j in range(b):
        key[i] += pow(2,c[j]-1)

INF = float('inf')

DP = [[INF]*(2**N) for i in range(M+1)]
DP[0][0] = 0
for i in range(M):
    for j in range(2**N):
        DP[i+1][j] = min(DP[i][j],DP[i+1][j])
        DP[i+1][j|key[i]] = min(DP[i+1][j|key[i]],DP[i][j]+cost[i],DP[i][j|key[i]])

if DP[M][2**N-1]>10**27:
    print(-1)
else:
    print(DP[M][2**N - 1])

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
a = []
b = []
for i in range(m):
    aa,bb = inm()
    cc = inl()
    a.append(aa)
    x = 0
    for j in range(bb):
        x += 2**(cc[j]-1)
    b.append(x)

ddprint(a)
ddprint(b)

t = [BIG]*(2**n)
t[0] = 0
for i in range(m):
    for j in range(2**n-1):
        if t[j]<BIG:
            t[j|b[i]] = min(t[j|b[i]], t[j]+a[i])
if t[2**n-1]==BIG:
    print(-1)
else:
    print(t[2**n-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ab = []
c = []
def bit(ls):
    res = 0
    for elem in ls:
        res += 2**(elem-1)
    return res

for i in range(M):
    ab.append(list(map(int,input().split())))
    l = list(map(int,input().split()))
    val = bit(l)
    c.append(val)
dp = [10**6]*(2**N)
dp[0] = 0
for i in range(M):
    for j in range(2**N):
        dp[c[i] | j] = min(dp[c[i] | j], dp[j]+ab[i][0])
if dp[2**N-1] == 10**6:
    print(-1)
else:
    print(dp[2**N-1])

Submission status: Accepted

Solution code:
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()])
    # print(c)
    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)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc142/submissions/7777847

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
lis = []
for _ in range(M):
    a,b = map(int,input().split())
    C = list(map(int,input().split()))
    s = 0
    for c in C:
        s |= 1 << (c-1) #その鍵が開けられる宝箱に応じてビットシフト
    # |は論理和（ ビット演算での+ ）
    lis.append((s,a))

dp = [float("inf")]*(2**N)  #2**N == 1<<N
dp[0] = 0
#下から積み上げていくdp、bitDPではset()の代わりに|が使える
for bit in range(2**N):
    for i in range(M):
        s,a = lis[i]
        t = bit | s
        dp[t] = min(dp[t],dp[bit]+a)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

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

dp[0]=0

for _ in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    cl=["0"]*N
    for item in c:
        cl[item-1]="1"
    plus=int(str("".join(cl)),2)
    for i in range(len(dp))[::-1]:
        if dp[i]!=10**9:
            #print(i,i|plus)
            dp[i|plus]=min(dp[i|plus],dp[i]+a)
if dp[-1]!=10**9:
    print(dp[-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
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 cc in c:
    tmp += 2 ** (cc - 1)
  A.append(a)
  C.append(tmp)
#print(A)
#print(C)

INF = 10 ** 15
dp = [INF for _ in range(2 ** N)]# dp[開閉のbit] = min(コスト)
dp[0] = 0

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

Submission status: Accepted

Solution code:
from itertools import product
N,M = map(int,input().split())
G = {i:[] for i in range(M)}
for i in range(M):
    a,b = map(int,input().split())
    G[i] = [a,list(map(int,input().split()))]
INFTY = 10**11
dp = [[INFTY for S in range(2**N)] for _ in range(M+1)]
for j in range(M+1):
    dp[j][0] = 0
for j in range(M):
    for S in range(2**N):
        y = 0
        for x in G[j][1]:
            y += 2**(x-1)
        dp[j+1][S] = min(dp[j][S],dp[j][S&(~y)]+G[j][0])
a =dp[M][2**N-1]
if a>=INFTY:
    print(-1)
else:
    print(a)

Submission status: Accepted

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

dp = [float('inf')] * 2**n

dp[0]=0

for i in range(m):
    a,b = map(int, input().split())
    c = list(map(int, input().split()))
    key = 0
    for j in c:
        key+=2**(j-1)
    for j in range(len(dp)):
        dp[j|key] = min(dp[j|key], dp[j]+a)

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

Submission status: Accepted

Solution code:
#import sys
#def input():
#  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
A=[0]*(m+1); S=[0]*m

for i in range(m):
    a,b=map(int,input().split())
    A[i]=a
    s=0
    for ci in map(int,input().split()):
        s|=1<<(ci-1)
    S[i]=s
dp=[[inf]*(2**n) for i in range(m+1)]
for i in range(m+1):
    dp[i][0]=0
# print(dp)
# print(S)
for i in range(m):
    for s in range(2**n):
        dp[i+1][s]=min(dp[i+1][s],dp[i][s])
        # if i==1 and s==0:
        #     print(i,s,S[i])
        #     print(dp[i+1][s|S[i]],dp[i+1][s|S[i]],dp[i][s|S[i]],dp[i][s]+A[i])
        dp[i+1][s|S[i]]=min(dp[i+1][s|S[i]],dp[i][s|S[i]],dp[i][s]+A[i])
print(dp[m][(1 << n)-1] if dp[m][(1 << n)-1] != inf else -1)
# print(S)
# for di in dp:
#     print(*di)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
key = []
key_i = []
for i in range(M):
  key.append(list(map(int, input().split())))
  key_i.append(list(map(int, input().split())))
keybin = [0]*M
for j in range(M):
  for x in key_i[j]:
    keybin[j] += 2**(x-1)
INF = float("inf")
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):
    x = keybin[i-1]
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    DP[i][j|x] = min(DP[i][j|x],DP[i-1][j|x], DP[i-1][j]+key[i-1][0])
if DP[-1][-1] >10**18:
  print(-1)
else:
  print(DP[-1][-1])

Submission status: Accepted

Solution code:
MAX = 10**8+1
N, M = map(int, input().split())

X = [MAX]*(2**N)
X[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    k = sum(1<<(c-1) for c in map(int, input().split()))

    for j, x in enumerate(X):
        if X[j|k] > x + a:
            X[j|k] = x + a

print(X[-1] if X[-1] < MAX else -1)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
ab=[]
c=[]
li=[0]*n
for i in range(m):
    ab.append(list(map(int,input().split())))
    c.append(list(map(int,input().split())))
    for j in range(len(c[i])):
        li[c[i][j]-1]+=1
if min(li)==0:
    print(-1)
    exit()
dp=[[float('inf')]*(2**n) for i in range(2)]
for i in range(2):
    dp[i][0]=0

li=[]
for i in range(m):
    tmp=0
    for j in range(ab[i][1]):
        tmp+=2**(c[i][j]-1)
    li.append(tmp)
# print(li)
# print(dp)
# print(2**n)
for i in range(m):
    for j in range(2**n):
        # tmp=j|li[i]
        # print(i,j,li[i],tmp)
        dp[i+1][j|li[i]]=min(dp[i+1][j|li[i]],dp[i+1][j]+ab[i][0])
        dp.append(dp[-1])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
LE = 1 << N
DP = [10**15]*(LE)
DP[0] = 0

for _ in range(M):
    a,b=LI()
    key = 0
    for i in LI():
        key |= 1<<(i-1)
    for j in range(LE):
        DP[j | key] = min(DP[j | key], DP[j] + a)

res = DP[(1 << N) - 1]
print(res if res != 10**15 else -1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [inf for i in range(2**N)]
dp[0] = 0
for i in range(1,M+1):
    dp[C[i]] = min(dp[C[i]],A[i])
    for j in range(2**N):
        k =  j|C[i]
        dp[k] = min(dp[k],dp[j]+A[i])
if dp[2**N-1] == inf:
    dp[2**N-1] = -1
print(dp[2**N-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = []
    c = []
    for i in range(m):
        d,b = LI()
        e = LI_()
        a.append(d)
        t = 0
        for u in e:
            t |= 2**u
        c.append(t)

    d = collections.defaultdict(lambda: inf)
    d[0] = 0
    for i in range(m):
        ai = a[i]
        ci = c[i]
        for k,v in list(d.items()):
            nk = k | ci
            nv = v + ai
            if d[nk] > nv:
                d[nk] = nv
    if d[2**n-1] == inf:
        return -1

    return d[2**n-1]


print(main())

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = [] # 鍵が空けることのできる宝箱(bit表現)
C = [] # 鍵のコスト
for _ in range(m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  C.append(a)
  s = sum([2 ** (i - 1) for i in c])
  S.append(s)

# dp：それぞれの鍵について、空けることができる(1)/できない(0)の二つの状態を表す。
INF = 10 ** 19
dp = [INF] * (1 << n) # 1 << n は2 ** n と同じ
dp[0] = 0
for s, c in zip(S, C):
  for i in range(1 << n):
    j = i | s # jは鍵を使った後の状態。 i -> (sを開ける) -> j 
    x = dp[i] + c
    dp[j] = min(dp[j], x)
    
ans = dp[-1]
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [[INF]*(2**n) for i in range(m+5)]
for i in range(m+1):
    dp[i][0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for j in range(2**n):
        dp[i+1][j] = min(dp[i][j], dp[i][j&(~key)]+val)
        
res = dp[m][2**n-1]
print(res if res != INF else -1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [INF]*(2**n)
dp[0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for _ in range(2**n):
        dp[_|key] = min(dp[_|key], dp[_]+val)
        
res = dp[-1]
print(res if res != INF else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
ALL=1<<N
dp=[10**9]*ALL
dp[0]=0
#print(dp)
for i in range(M):
    ndp=dp[:]
    #print(ndp)
    a,b=map(int,input().split())
    c=[int(i)-1 for i in input().split()]

    C=0
    for i in c:
        C|=1<<i

    for S in range(ALL):
        ndp[S|C]=min(ndp[S|C],dp[S]+a)
    dp=ndp
#print(dp)
if dp[-1]==10**9:print(-1)
else:print(dp[-1])

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    md = pow(2, n)
    dp = [10 ** 15] * md
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, readline().split()))
        c = sum([2 ** (v - 1) for v in list(map(int, readline().split()))])
        for j in range(md):
            dp[j | c] = min(dp[j | c], dp[j] + a)
    print(dp[-1] if dp[-1] != 10 ** 15 else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[0]*(M+1)
b=[0]*(M+1)
c=[[] for _ in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))

 #各鍵で明けられる宝箱のbit列
d=[0]*M
for i in range(M):
    for cij in c[i]:
        d[i]+=pow(2,cij-1)

inf=10**9
#dp[i][j]はi番目の鍵で状態jにたどり着く時に必要な最小コスト
dp = [[inf]*pow(2,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(pow(2,N)):
        dp[i+1][j|d[i]] =min(dp[i+1][j|d[i]] , dp[i][j]+a[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a,b=[0]*M,[0]*M
    c=[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
        l=list(map(int,input().split()))
        for box in l:
            c[i]=c[i]|(1<<(box-1))
    dp=[[INF]*(2**N) for _ in range(M+1)]
    dp[0][0]=0
    for i in range(M):
        for boxes in range(2**N):
            dp[i+1][boxes]=min(dp[i+1][boxes],dp[i][boxes])
            dp[i+1][boxes|c[i]]=min(dp[i+1][boxes|c[i]],dp[i][boxes]+a[i])
    print(dp[M][2**N-1] if dp[M][2**N-1]!=INF else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
b = []
c = []

import sys
sys.setrecursionlimit(2000)

for i in range(M):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    ci = list(map(int, input().split()))
    c.append(ci)

c_bin = [0] * M
for j in range(M):
    for k in range(b[j]):
        c_bin[j] |= (1 << (c[j][k] - 1))

ceil = 1 << N
memo = [None] * (ceil * (M + 1))
# print("#", '[' +' '.join(map(lambda x: '0b{:b}'.format(x), c_bin)) + ']', ceil)
def dp(pos, state):
    global M, ceil
    idx = pos * ceil + state
    # print("##", pos, '0b{:b}'.format(state), idx)
    if state == ceil - 1:
        ret = 0
    elif pos == M:
        ret = -1
    elif memo[idx] != None:
        return memo[idx]
    else:
        ret0 = dp(pos + 1, (state | c_bin[pos]))
        ret1 = dp(pos + 1, state)
        if ret0 == ret1 == -1:
            ret = -1
        elif ret1 == -1:
            ret = a[pos] + ret0
        else:
            ret = min(a[pos] + ret0, ret1)
    #
    memo[idx] = ret
    return ret

print(dp(0, 0))

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    INF = 10 ** 9
    
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        c = list(map(lambda x: int(x) - 1, input().split()))
        open = 0
        for i in range(b):
            open += 1 << c[i]
        for i in range(2 ** N):
            if dp[i] + a <= dp[i | open]:
                dp[i | open] = dp[i] + a
    
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import product
def main():
    N, M = map( int, input().split())
    costs = [0]*M
    keys = [0]*M
    for i in range(M):
        costs[i], b = map( int, input().split())
        C = list( map( int, input().split()))
        key = 0
        for c in C:
            key += pow(2, c-1)
        keys[i] = key
    K = pow(2,N)
    dp =[10**7]*K
    dp[0] = 0
    for i in range(M):
        key = keys[i]
        cost = costs[i]
        for j in range(K):
            if j != (j | key):
                if dp[j] + cost < dp[j|key]:
                    dp[j|key] = dp[j] + cost
    if dp[K-1] == 10**7:
        print(-1)
    else:
        print(dp[K-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m = map(int, input().split())
    ab = []
    c = []

    for i in range(m):
        ab.append(list(map(int, input().split())))
        c.append(list(map(int, input().split())))

    for i in range(m):
        temp = 0
        for j in range(len(c[i])):
            temp += 2**(c[i][j]-1)
        c[i] = temp
        # c[i]=(("0"*n)+bin(temp)[2:])[-n:]

    dp = dict()

    for i in range(2**n):
        dp[i] = 10**9
        # dp[(("0"*n)+bin(i)[2:])[-n:]]=-1

    dp[0] = 0

    # print(dp)
    for i in range(m):
        for k, item in dp.items():
            dp[c[i] | k] = min(dp[c[i] | k], dp[k]+ab[i][0])

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

main()

Submission status: Accepted

Solution code:
import math

nm = list(map(int, input().split()))
N, M = nm[0], nm[1]
dp = [1145141919810 for i in range(int(math.pow(2, N)))]
dp[0] = 0
for i in range(M):
    c_num = list(map(int, input().split()))
    cost, NUM = c_num[0], c_num[1]
    index = 0
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        index += int(math.pow(2, tmp[j] - 1))
    for j in range(int(math.pow(2, N))):
        dp[j | index] = min(dp[j | index], dp[j] + cost)
if dp[len(dp) - 1] == 1145141919810:
    print(-1)
else:
    print(dp[len(dp) - 1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
inf=10**9
 
n,m=map(int, input().split())
 
dp=[[inf for _ in range(2**n)] for _ in range(m+1)]
dp[0][0]=0
 
for i in range(1, m+1):
    a,b=map(int, input().split())
 
    state=0
    c=list(map(int, input().split()))
    for x in c:
        state+=(1<<(x-1))
    
    for j in range(2**n):
        dp[i][j]=min(dp[i][j], dp[i-1][j])
        dp[i][j|state]=min(dp[i][j|state], dp[i-1][j|state], dp[i-1][j]+a)
 
if dp[m][2**n-1] == inf:
    print(-1)
    exit()
print(dp[m][2**n-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
cost=[0]*m
keys=[0]*m
for i in range(m):
  a,b=map(int,input().split())
  cost[i]=a
  k=list(map(int,input().split()))
  for j in range(b):
    keys[i]|=(1<<(k[j]-1))

INF=10**9+1
dp=[INF]*(2**n)
dp[0]=0
for i in range(len(keys)):
  for j in range(len(dp)-1,-1,-1):
    if dp[j]!=INF:
      if dp[j|keys[i]]>dp[j]+cost[i]:
        dp[j|keys[i]]=dp[j]+cost[i]

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
cost=[0]*m
keys=[0]*m
for i in range(m):
  a,b=map(int,input().split())
  cost[i]=a
  k=list(map(int,input().split()))
  for j in range(b):
    keys[i]|=(1<<(k[j]-1))

INF=10**9+1
dp=[INF]*(2**n)
dp[0]=0
for i in range(len(keys)):
  for j in range(len(dp)-1,-1,-1):
    if dp[j]!=INF:
      dp[j|keys[i]]=min(dp[j|keys[i]],dp[j]+cost[i])
if dp[-1]!=INF:
  print(dp[-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    KV=[None]*m
    for i in range(m):
        K=0
        a,b=map(int,input().split())
        for c in map(int,input().split()):
            c-=1
            K|=1<<c
        KV[i]=(K,a)

    N=1<<n
    dp=[INF]*N
    dp[0]=0
    for K,v in KV:
        ndp=dp[:]
        for i in range(N):
            ndp[i|K]=min(ndp[i|K],dp[i]+v)
        dp=ndp

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