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 pypy

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

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

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[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()))

        # 開錠可能な箱をbitで表現する
        bit = 0
        for x in c:
            bit |= 1 << (x-1)
        
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
c=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
  c.append(list(map(int,input().split())))
dp={'0'*n:0}
for i in range(m):
  a,b=ab[i]
  ci=c[i]
  dptmp={}
  for k,v in dp.items():
    s=list(k)
    for cii in ci:
      s[cii-1]='1'
    t=''.join(s)
    dptmp[t]=min(v+a,dp[t] if t in dp else float('inf'),dptmp[t] if t in dptmp else float('inf'))
  dp.update(dptmp)

t='1'*n
if t in dp:
  print(dp[t])
else:
  print(-1)
#print(dp)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = []
Y = []
for _ in range(M):
    X.append(list(map(int, input().split())))
    
    tmp = 0
    for i in list(map(int, input().split())):
        tmp += 2 ** (i - 1)
    Y.append(tmp)

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

ans = min(dp[i][-1] for i in range(M + 1))
print(ans if ans < inf else -1)

Submission status: Accepted

Solution code:
ans = 10 ** 7
n, m = map(int, input().split())
dp = [float('inf')] * (2 ** n)
dp[0] = 0
prices = []
for i in range(m):
    a, s = map(int, input().split())
    prices.append(a)
    f = 0
    for k in map(int, input().split()):
        f += 2 ** (k - 1)
    for j in range(2 ** n - 1, -1, -1):
        dp[j | f] = min(dp[j] + a, dp[j | f])
print(-1 if dp[-1] == float('inf') else dp[-1])

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    n,m = invr()
    q = 1 << n
    w = [10 ** 18] * q
    w[0] = 0
    for i in range(m):
        a,b = invr()
        qw = 0
        for j in map(int,input().split()):
            qw = qw + (1 << (j - 1))
        for j in range(q - 1,-1,-1):
            w[j|qw] = min(w[j] + a,w[j | qw])
    print(-1 if w[-1] == 10 ** 18 else w[-1])
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    n, m = map(int, input().split())
    key = []  # 集合S，コスト
    for i in range(m):
        a, b = map(int, input().split())
        s = 0
        C = list(map(int, input().split()))
        for j in range(b):
            C[j] -= 1
            s |= 1 << C[j]  # C[j]桁目のbitを1にする
        key.append((s, a))
    INF = 10**9+7
    dp = [INF]*(2**n)
    dp[0] = 0

    for s in range(2**n):
        for i in range(m):
            t = s | key[i][0]
            cost = dp[s]+key[i][1]
            dp[t] = min(dp[t], cost)

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


resolve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
keys = []
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
    keys.append((s, a))

INF = 1001001001
dp = [INF] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for k, v in keys:
        t = s | k
        cost = dp[s] + v
        dp[t] = min(dp[t], cost)

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

Submission status: Accepted

Solution code:
def main():
    INF = 10 ** 10
    N, M = list(map(int, input().split(' ')))
    key_list = list()
    for _ in range(M):
        A, _ = list(map(int, input().split(' ')))
        C = list(map(lambda x: int(x) - 1, input().split(' ')))
        boxes = 0
        for c in C:
            boxes |= (1 << c)
        key_list.append((A, boxes))
    # bit DP
    # dp[m][S]: m個目までのカギでSに含まれる宝箱を開けるための最小費用
    dp = [[INF for _ in range(1 << N)] for _ in range(M + 1)]
    for m in range(M + 1):
        dp[m][0] = 0
    for m in range(1, M + 1):
        cost, box = key_list[m - 1]
        for S in range(1 << N):
            dp[m][S] = min(dp[m][S], dp[m - 1][S])
            if box | S != S:
                dp[m][box | S] = min(dp[m][box | S], dp[m - 1][S] + cost)
    ans = dp[M][(1 << N) - 1]
    if ans >= INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [float("INF")]*(1<<n)
dp[0] = 0
for _ in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    C = 0
    for e in c:
        C += 1<<(e-1)
    for i in range(1<<n): 
        dp[i|C] = min(dp[i|C], dp[i]+a)
if dp[-1] == float("INF"): print(-1)
else: print(dp[-1])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = sum(1 << (int(s) - 1) for s in readline().split())

    dp = [INF] * (1 << N)
    dp[0] = 0
    for S in range(1 << N):
        if dp[S] == INF:
            continue
        for a, c in zip(A, C):
            if dp[S | c] > dp[S] + a:
                dp[S | c] = dp[S] + a

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = sum(1 << (int(s) - 1) for s in readline().split())

    dp = [[INF] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            if dp[i + 1][j] > dp[i][j]:
                dp[i + 1][j] = dp[i][j]
            if dp[i + 1][j | C[i]] > dp[i][j] + A[i]:
                dp[i + 1][j | C[i]] = dp[i][j] + A[i]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = ~sum(1 << (int(s) - 1) for s in readline().split())

    dp = [INF] * (1 << N)
    dp[0] = 0
    for bit in range(1 << N):
        for a, c in zip(A, C):
            if dp[bit & c] < INF:
                dp[bit] = min(dp[bit], dp[bit & c] + a)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = sum(1 << (int(s) - 1) for s in readline().split())

    dp = [INF] * (1 << N)
    dp[0] = 0
    for bit in range(1 << N):
        for a, c in zip(A, C):
            if dp[bit & ~c] < INF:
                dp[bit] = min(dp[bit], dp[bit & ~c] + a)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
INF=10**10
dp=[[INF]*(1<<n) for _ in range(m+1)]
for i in range(m+1):
    dp[i][0]=0
a=[0]
key=[0]
for i in range(m):
    a0,b=map(int,input().split())
    a.append(a0)
    *c,=map(int,input().split())
    tmp=0
    for j in c:
        tmp+=1<<(j-1)
    key.append(tmp)

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

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=(1<<n)
dp=[10**18]*g
dp[0]=0
for i in  range(m):
    a,s=map(int,input().split())
    f=0
    for k in map(int,input().split()):
        f+=1<<(k-1)
    for j in range(g-1,-1,-1):
        dp[j|f]=min(dp[j]+a,dp[j|f])
print(-1 if dp[-1]==10**18 else dp[-1])

Submission status: Accepted

Solution code:
ans=10**7
n,m=map(int,input().split())
dp=[10**18]*(2**n)
dp[0]=0
prices=[]
for i in  range(m):
    a,s=map(int,input().split())
    prices.append(a)
    f=0
    for k in map(int,input().split()):
        f+=2**(k-1)
    for j in range(2**n-1,-1,-1):
        dp[j|f]=min(dp[j]+a,dp[j|f])
print(-1 if dp[-1]==10**18 else dp[-1])

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
inf=10**10
dp=[[inf]*(2**N) for _ in range(M+1)]
dp[0][0]=0

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

    s=0
    for cc in c:
        s+=2**(cc-1)
    
    for j in range(2**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]+a)
    
print(dp[M][2**N-1] if dp[M][2**N-1]<inf else -1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
weight = []
value = []
for i in range(M):
    a, b = getNM()
    c = getList()
    weight.append(a)
    value.append(c)
"""
N, M = 4, 6
weight = [67786, 3497, 44908, 2156, 26230, 86918]
value = [[1, 3, 4], [2], [2, 3, 4], [2, 3, 4], [2], [3]]
"""

# N個のものを全て手に入れるのに必要なコストの最小値
# コストを1にすれば最小個数がわかる
# Nの数が十分に小さいと使用可能
def get_everything(n, weight, value):
    m = len(weight)
    dp = [float("inf")] * (1 << n)
    dp[0] = 0

    for i in range(m):
        bit = 0
        for item in value[i]:
            bit |= (1 << (item - 1))

        for j in range(1 << n):
            dp[j | bit] = min(dp[j | bit], dp[j] + weight[i])

    return dp[(1 << N) - 1]

ans = get_everything(N, weight, value)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

keys=[[] for _ in range(N)]
dp=[-1]*(2**N)
dp[0]=0

for _ in range(M):
    a,b=list(map(int,input().split()))
    c=list(map(int,input().split()))

    op=2**N-1

    for cc in c:
        op-=2**(cc-1)

    for cc in c:
        keys[cc-1].append((op,a))


def rec(current):
    if dp[current]>-1:
        return dp[current]

    ret=10**10

    i=0
    tmp=current
    while tmp&1==0:
        i+=1
        tmp=tmp>>1
    
    for op,a in keys[i]:
        minc=rec(current&op)
        ret=min(ret,a+minc)
    
    if ret==10**10:
        print(-1)
        exit(0)
    
    dp[current]=ret
    return ret

print(rec(2**N-1))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a, b, c = [], [], []
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)

dp = [[10**9 for j in range(2**n)] for i in range(m)]
key = 0
for i in range(b[0]):
    key += 1<<(c[0][i]-1)
dp[0][key] = a[0]
dp[0][0] = 0

for i in range(1, m):
    ai, bi, ci = a[i], b[i], c[i]
    key = 0
    for j in range(bi):
        key += 1<<(ci[j]-1)
    for j in range(2**n):
        dp[i][j|key] = min(dp[i-1][j|key], dp[i-1][j]+ai, dp[i][j|key])
    for j in range(2**n):
        dp[i][j] = min(dp[i-1][j], dp[i][j])

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a, b, c = [], [], []
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)

dp = [[10**9 for j in range(2**n)] for i in range(m)]
for i in range(m):
    dp[i][0] = 0
key = 0
for i in range(b[0]):
    key += 1<<(c[0][i]-1)
dp[0][key] = a[0]

for i in range(1, m):
    ai, bi, ci = a[i], b[i], c[i]
    key = 0
    for j in range(bi):
        key += 1<<(ci[j]-1)
    for j in range(2**n):
        dp[i][j|key] = min(dp[i-1][j|key], dp[i-1][j]+ai, dp[i][j|key])
    for j in range(2**n):
        dp[i][j] = min(dp[i-1][j], dp[i][j])

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

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7


n,m=MI()
data=[]
for i in range(m):
    a,b=MI()
    c=LI()
    u=0
    for x in c:
        u+=2**(x-1)
    data.append([a,u])
data.sort()
#print(data)
dp=[[inf]*(2**n) for i in range(m+1)]
dp[0]=[inf]*(2**n)
dp[0][0]=0
#print(dp)
for i in range(m):
    for j in range(2**n):
        dp[i+1][j|data[i][1]]=min(dp[i+1][j|data[i][1]],dp[i][j|data[i][1]],dp[i][j]+data[i][0])
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        #print(i+1,j|data[i][1],dp[i][j|data[i][1]],dp[i][j]+data[i][0])
    #print()
#print(dp)
if dp[-1][-1]>=inf:
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[]
INF=10**9
for i in range(m+1):
  dp.append([])
  dp[-1].append(0)
  for j in range(2**n-1):
    dp[-1].append(INF)
keys=[]
for i in range(m):
  a,b=map(int,input().split())
  r=['0']*n
  c=list(map(int,input().split()))
  for j in range(b):
    r[c[j]-1]='1'
  s=''.join(r)
  keys.append([int(s,2),a])
    
for i in range(m):
  for j in range(2**n):
    dp[i+1][j|keys[i][0]]=min(dp[i+1][j|keys[i][0]],dp[i][j]+keys[i][1])
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
if dp[m][2**n-1]==10**9:
  print(-1)
else:
  print(dp[m][2**n-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

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

K = []
for _ in [0]*M:
    a, b = map(int, input().split())
    *C, = map(int, input().split())
    h = 0
    for c in C:
        h ^= 1 << (c-1)
    
    for i in range(1<<N):
        nxt = i|h
        dp[nxt] = min(dp[nxt], dp[i]+a)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
v = []
t = []

for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    v.append(a)
    ti = 0
    
    for i in range(b):
        ti += 1<<(c[i]-1)
    
    t.append(ti)

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

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

if dp[-1]==10**18:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
INF=10**18
dp=[INF]*(1<<N)
dp[0]=0
cost=[None]*M
target=[0]*M

for i in range(M):
    cost[i],b=map(int,input().split())
    
    c=[int(x) for x in input().split()]
    for j in c:
        target[i]=target[i]|(1<<(j-1))
    
for s in range(1<<N):
    for i in range(M):
        ns=s|target[i]
        dp[ns]=min(dp[ns],dp[s]+cost[i])
if dp[-1]==INF:
    print(-1)
else :
    print(dp[-1])

Submission status: Accepted

Solution code:
INF = 10**10

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

key = [[]]#index調整のために一ついれとくわ
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    tmp=0
    for i in range(0,b,1):
        tmp += pow(2,c[i]-1)
    key.append([a,tmp])#key[2]で開けられる宝箱について表す。一つも開けられないなら0 一つ目だけ開けられるなら1　2:2 3:4 4:8

#DP[i][j] i個目までのなかで状態jにするために必要な値段の最小値（不可能なら INF）

DP = [[INF for i in range(0,pow(2,N),1)] for j in range(0,M+1,1)]
for i in range(0,M+1,1):
    DP[i][0]=0 #一つも開けていない状態には0円で到達可能

for i in range(0,M,1):
    cost,openable = key[i+1][0],key[i+1][1]


    for j in range(0,pow(2,N),1):
        if DP[i][j]!=INF:
            DP[i+1][j | openable] = min(DP[i+1][j | openable],DP[i][j]+cost) #買う
            DP[i+1][j] = min(DP[i+1][j],DP[i][j]) #買わない

print(DP[M][pow(2,N)-1] if DP[M][pow(2,N)-1]!=INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
keys = [None] * M
for i in range(M):
  cost,b = map(int,readline().split())
  bit = 0
  target = list(map(int,readline().split()))
  for t in target:
    bit += (1 << (t - 1))
  keys[i] = (cost, bit)
    
# 全ての鍵の組み合わせでDP
INF = 10 ** 8 + 1
dp = [INF for i in range(2 ** N)]
dp[0] = 0
for key in keys:
  cost, bit = key
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    if dp[j | bit] > dp[j] + cost:
      dp[j | bit] = dp[j] + cost

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
keys = [None] * M
for i in range(M):
  cost,b = map(int,readline().split())
  bit = 0
  target = list(map(int,readline().split()))
  for t in target:
    bit += (1 << (t - 1))
  keys[i] = (cost, bit)
    
# 全ての鍵の組み合わせでDP
INF = 10 ** 8 + 1
dp = [INF for i in range(2 ** N)]
dp[0] = 0
for key in keys:
  cost, bit = key
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == -1:
      continue
    if dp[j | bit] > dp[j] + cost:
      dp[j | bit] = dp[j] + cost

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
dp = [float("inf")] * (1 << N)
dp[0] = 0

# 1 ~ Nを全て開けられる鍵を揃えるコストの最小値がO(M * 2 ** N)でわかる
# 各鍵について
for i in range(M):
    a, b = getNM()
    c = getList()
    bit = 0
    # その鍵で開けられる部屋を揃える
    for item in c:
        bit |= (1 << (item - 1))
    # 部屋の各状態について
    # そこからさらに鍵cを取得した場合と他の鍵を使用した場合とで比較する
    for j in range(1 << N):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[[] for i in range(m)]
for i in range(m):
  a[i],b[i] =map(int,input().split())
  c[i] = sum([2**(int(x)-1) for x in input().split()])
# N
dp = [1000000000 for i in range(2**n)]
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|c[j]] = min(dp[i|c[j]], dp[i]+a[j])
if dp[2**n-1]==1000000000:
  print(-1)
else:
  print(dp[2**n-1])

Submission status: Accepted

Solution code:
def chmin(l, i, v):
  if l[i] > v:
    l[i] = v
    return True
  return False

def main():
    N, M = map(int, input().split())
    keys = []
    for i in range(M):
        a, b = map(int, input().split())
        C = map(int, input().split())
        # mask: nビット目が1なら、n番目のカギを開けられる
        mask = 0
        for c in C:
            mask |= 1 << (c-1)
        keys.append((a, mask))
    
    # N 個のカギを選ぶ、選ばないのパターンを考えると、その組み合わせは2^N 通り
    # コスト無限大で初期化
    patterns = 1 << N
    INF = float("inf")
    # dp[i]: iのnビット目が1なら、n番目のカギを開けられて、その開けられるカギの組み合わせでの最安値を示している
    # 例: dp[3]: 1番目と2番目のカギをあけたいときの最安値
    dp = [ INF ] * patterns
    dp[0] = 0

    # 計算量: O(2^N * M) => 最大でも 4096 * 10^3 ~= 10^6
    for a, mask in keys:
        for i in range(patterns):
            chmin(dp, i|mask, dp[i] + a)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 10**18

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

A = []
B = []
C = []

for _ in range(M):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)
    c = tuple(map(int,input().split()))
    C.append(c)
    
dp = [[INF for j in range(2**N)] for i in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    s = 0
    for k in range(B[i]):
        s += 2**(C[i][k] - 1)
    for j in range(2**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] + A[i])
        
res = dp[M][2**N - 1]

print(res if res != INF else -1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
keys = []
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  s = 0
  for cc in c:
    cc -= 1
    s |= 1<<cc
  keys += [(s, a)]

dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | keys[i][0]
    dp[t] = min(dp[t], keys[i][1]+dp[s])

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

Submission status: Accepted

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

dp = [10**10 for B in range(1 << N)]
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = [int(j) for j in input().split()]
    C = sum([1 << (x-1) for x in c])

    for B in range(1 << N):
        dp[B | C] = min(dp[B | C], dp[B]+a)

if dp[(1 << N)-1] == 10**10:
    print(-1)
else:
    print(dp[(1 << N)-1])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

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

    for i in range(M):
        num, a = key[i]
        for j in range(2**N):
            next_num = j | num
            dp[next_num] = min(dp[next_num], dp[j] + a)

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
  N, M = map(int, input().split())
  inf =  10**9
  p = 1<<N
  dp = [inf]*p 
  dp[0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([1<<(c-1) for c in C])
    for j in range(p):
      #print(min(dp[i][j|c_bit], dp[i][j] + a))
      dp[j|c_bit] = min(dp[j|c_bit], dp[j] + a)
  if dp[p-1] == inf:
    print(-1)
  else: 
    print(int(dp[p-1]))
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  N, M = map(int, input().split())
  inf =  10**15
  p = 1<<N
  dp = [inf]*p
  dp[0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    c = sum(1<<(i-1) for i in map(int, input().split()))
    for j in range(p):
      dp[c|j] = min(dp[j]+a, dp[c|j])
  if dp[-1] == inf:
    print(-1)
  else: 
    print(int(dp[-1]))
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

for i in range(m):
    a_, b_ = map(int, input().split())
    c_ = list(map(int, input().split()))
    a.append(a_)
    b.append(b_)
    val = 0
    for _c_ in c_:
        val += 2 ** (_c_ -1)
    c.append(val)

max_m = 2**n

dp = [[float('inf')] * max_m for _ in range(m+1)]
dp[0][0]=0

# print(c)

for i in range(1, m+1):
    for combi in range(max_m):
        # print(c[i-1])
        combi_diff = 0
        combi_diff = combi & ~c[i-1]
        dp[i][combi] = min(dp[i-1][combi], dp[i-1][combi_diff] + a[i-1])

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

Submission status: Accepted

Solution code:
from functools import reduce
N, M = map(int, input().split())
L = 1 << N
table = {0: 0}
for _ in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l, now in table.copy().items():
        table[l | match] = min(now + cost, table.get(l | match, 10 ** 7))
print(table[L - 1] if table.get(L - 1, False) else -1)