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:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    ABC = []
    for _ in range(m):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        s = ["0"] * n
        for c in C:
            s[c - 1] = "1"

        c = "".join(s[::-1])
        ABC.append([a, b, int(c, 2)])

    dp = [f_inf for _ in range(1 << n)]
    dp[0] = 0
    for a, b, c in ABC:
        for i in range(1 << n):
            idx = i | c
            dp[idx] = min(dp[idx], dp[i] + a)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

ab = []
c = []
for _ in range(m):
    ab_i = tuple(map(int,input().split()))
    ab.append(ab_i)
    c_i = tuple(map(int,input().split()))
    c_i_bit = 0
    for j in c_i:
        c_i_bit += 1 << (j-1)
    c.append(c_i_bit)

inf = 10**10
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|c[i]] = min(dp[i+1][j|c[i]], dp[i][j] + ab[i][0])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
inf = int(1e10)
dp = [inf] * (1 << N) #1をNだけシフトする 2**B

#鍵をビットで表す　dp[i]は鍵の状態iにできる最小費用を
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()))
    # cを状態keyに変換
    key = 0
    for t in c:
        key += 1 << (t - 1)
    # bits内のbitとkeyのORを更新
    # 更新したbitはbitsに追加
    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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
E - Get Everything
https://atcoder.jp/contests/abc142/tasks/abc142_e

"""
import sys


def solve(N, M):
    dp = [float('inf')] * 2**N
    dp[0] = 0
    for y in range(1, M+1):
        a, b = map(int, input().split())
        c = [int(i) for i in input().split()]
        t = 0
        for cc in c:
            t |= (1 << (cc-1))
        for x in range(2**N):
            if dp[x|t] > dp[x] + a:
                dp[x|t] = dp[x] + a
    return -1 if dp[-1] == float('inf') else dp[-1]


def main(args):
    N, M = map(int, input().split())
    ans = solve(N, M)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[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, b = 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 dp[-1] == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    C = list(map(int, input().split()))
    for c in C:
        c -= 1
        s |= 1 << c
    key.append((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)
ans = dp[-1]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    a=[0]*m
    c=[0]*m
    INF=10**9
    dp=[INF]*2**n
    for i in range(m):
        a[i]=int(input().split()[0])
        c[i]=sum([1<<(int(i)-1) for i in input().split()])
    dp[0]=0
    for i in range(2**n):
        for cos,pat in zip(a,c):
            npat=i|pat
            if dp[npat]>cos+dp[i]:
                dp[npat]=cos+dp[i]
    if dp[2**n-1]==INF:
        print(-1)
    else:
        print(dp[2**n-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    costs = [None]*m
    keys = [None]*m
    pattern = 2**n
    inf = 10**12
    dp = [inf]*pattern
    for i in range(m):
        costs[i] = int(input().split()[0])
        keys[i] = sum([1<<(int(i)-1) for i in input().split()])
    dp[0] = 0
    for i in range(pattern):
        for cost, key in zip(costs, keys):
            pi = i|key
            if dp[pi] > cost + dp[i]:
                dp[pi] = cost + dp[i]
    if dp[pattern-1] == inf:
        print(-1)
    else:
        print(dp[pattern-1])
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
COST = []
B = []
C = []
C_bit = []
INF = 10**18
dp = [INF]*(1<<N)
dp[0] = 0

for _ in range(M):
  a,b = map(int,input().split())
  C.append(list(map(int,input().split())))
  COST.append(a)
  B.append(b)

for i in range(M):
  bit = ['0']*N
  for j in range(B[i]):
    bit[C[i][j]-1] = '1'
  bit_int = int(''.join(bit),2)
  C_bit.append(bit_int)

for cost,c in zip(COST,C_bit):
  for i in range(1<<N):
    j = i|c
    d = dp[i]+cost
    if dp[j] > d:
      dp[j] = d

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def digit(n, m):
    n = str(n)
    while m - len(n):
        n = '0' + n
    return n

n, m = MAP()
dp = [[inf for _ in range(2 ** n)] for _ in range(m)]
for i in range(m):
    dp[i][0] = 0
for i in range(m):
    a, b = MAP()
    c = LIST()
    arr = [1 if i + 1 in c else 0 for i in range(n)]
    cnum = 0
    for j in range(n):
        cnum += arr[j] * (2 ** (n - j - 1))
    if i == 0:
        for j in range(1, 2 ** n):
            if (cnum ^ j) & j != 0:
                continue
            dp[i][j] = a
    else:
        for j in range(1, 2 ** n):
            former = (cnum & j) ^ j
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][former] + a)
    debug(dp[i])
if dp[m - 1][2 ** n - 1] >= inf:
    print(-1)
else:
    print(dp[m - 1][2 ** n - 1])

Submission status: Accepted

Solution code:
#ABC142-E Get Everything
"""
宝箱の制約が12個なので、これの状態を集合とする.
全ての状態について、(これはdpテーブルの状態ではない)
全ての鍵について考え、
この2つの状態のorで得られる状態sのdpテーブルをcost最小値で更新
そのようにして得られるdp[-1]が答えで、
この時O(2^N*M)がだいたい60**6なのでギリok
"""
import sys
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
INF = 10**10
cost_len_key = []
for i in range(m):
    a,b = map(int,readline().split())
    lst1 = list(map(int,readline().split()))
    res = 0
    for j in lst1:
        res += 1<<(j-1)
    cost_len_key.append([a,b,res])

#dp:状態s(か、s以上)の箱を開けた場合の最小コスト
dp = [INF for _ in range(1<<n)]
dp[0] = 0 #1つも開けていない状態はコスト0

for i in range(1<<n): #すべての状態について回す
    for j in cost_len_key: #すべての鍵について回す
        s = i|j[2] #状態=iの状態の宝箱が空いているときに、鍵jで追加して開ける時の状態
        dp[s] = min(dp[s],dp[i]+j[0]) #そのような状態の時のコストの最小値

ans = dp[-1] #全部の鍵が空いた時の最小コストが答え
if ans < INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
#ABC142-E Get Everything
"""
宝箱の制約が12個なので、これの状態を集合とする.
鍵をcost昇順に並べる。
ある鍵について、新たに埋められる場所が存在するなら、その鍵を使ってみる
"""
import sys
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
INF = 10**10
cost_len_key = []
for i in range(m):
    a,b = map(int,readline().split())
    lst1 = list(map(int,readline().split()))
    res = 0
    for j in lst1:
        res += 1<<(j-1)
    cost_len_key.append([a,INF-b,res])

cost_len_key.sort()

#dp:状態s(か、s以上)の箱を開けた場合の最小コスト
dp = [INF for _ in range(1<<n)]
dp[0] = 0

for i in range(1<<n):
    for j in cost_len_key:
        s = i|j[2]
        dp[s] = min(dp[s],dp[i]+j[0])

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

Submission status: Accepted

Solution code:
import sys
import itertools

N,M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(map(int, input().split())))
    C.append(sum(1<<(int(x)-1) for x in map(int, input().split())))

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

for n,((a,b),c) in itertools.product(range(1<<N), zip(AB,C)):
    m = n|c
    x = dp[n] + a
    if dp[m] > x:
        dp[m] = x

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

Submission status: Accepted

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

for _ in range(M):
    a, _ = map(int, input().split())
    k = 0
    for i in map(lambda a: int(a) - 1, input().split()):
        k |= (1 << i)
    K.append((a, k))

dp = [10**18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
    for a, k in K:
        if dp[state | k] > dp[state] + a:
            dp[state | k] = dp[state] + a
ans = dp[(1 << N) - 1]
print(ans if ans < 10**18 else -1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = [0]*m
C = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    c = list(map(int, input().split()))
    c = [x-1 for x in c]
    C[i] = c


dp = [10**18]*(2**n)
dp[0] = 0
C_bit = [0]*m
for i in range(m):
    C_bit[i] = 0
    for j in C[i]:
        C_bit[i] += 2**j

for i in range(2**n):
    for j in range(m):
        ni = i | C_bit[j]
        dp[ni] = min(dp[ni], dp[i]+A[j])

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = [[10**9]*(2**n+5) 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()))
    res = 0
    for x in c:
        res|=1<<(x-1)
    for j in range(2**n):
        ni = i+1
        nj = j|res
        dp[ni][j] = min(dp[ni][j],dp[i][j])
        dp[ni][nj] = min(dp[ni][nj],dp[i][j]+a)
ans = dp[m][2**n-1]
if ans == 10**9:ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    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-1)
        C.append(list(map(lambda x:int(x)-1, input().split())))

    #dp[i][j]=i番目の鍵まで見たとき、jの宝箱を開けられるようになった場合の費用の最小値
    dp = [[10**9] * (1<<N) for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        ni = i + 1
        nj = 0
        for c in C[i]: nj |= 1 << c
        for j in range(1<<N):
            dp[ni][j] = min(dp[ni][j], dp[i][j])
            dp[ni][j|nj] = min(dp[ni][j|nj], dp[i][j] + A[i])

    print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] < 10**9 else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
N, M = map(int, input().split())
inf = 10**18
dp = [inf]*(1<<N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    Cs = list(map(int, input().split()))
    bb = 0
    for c in Cs:
        bb += 2**(c-1)
    for x in range((1<<N)-1, -1, -1):
        dp[bb|x] = min(dp[x]+a, dp[bb|x])

#print(dp)
r = dp[(1<<N)-1]
if r != inf:
    print(dp[(1<<N)-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
valists = [10**9 for _ in range(1<<n)]
valists[0] = 0
for i in range(m):
	values, b = map(int, input().split())
	c = list(map(int, input().split()))
	cnt = 0
	for j in range(b):
		cnt += 2**(c[j]-1)
	for j in range(len(valists)):
		x = j|cnt
		valists[x] = min(valists[x], valists[j]+values)
		#print(j, cnt, x, valists)

#print(valists)
ans = valists[2**n-1]
if ans != 10**9:
	print(ans)
else:
	print(-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB, C = [], []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18

# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a, _), c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        state = i | c
        dp[state] = min(dp[state], dp[i] + a)

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

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    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-1)
        C.append(list(map(lambda x:int(x)-1, input().split())))

    #dp[i][j]=i番目の鍵まで見たとき、jの宝箱を開けられるようになった場合の費用の最小値
    dp = [[10**9] * (1<<N) for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        ni = i + 1
        for j in range(1<<N):
            dp[ni][j] = min(dp[ni][j], dp[i][j])
            nj = j
            for c in C[i]: nj |= 1 << c
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + A[i])

    print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] < 10**9 else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MY_INF = 1000000007

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

c_bin = []
for i in range(M):
    c_bin.append(sum([1 << (cij - 1) for cij in c[i]]))
    
memo = [None] * (1 << N)

def dp(state):
    global MY_INF
    if state == (1 << N) - 1: return 0
    if memo[state] != None: return memo[state]
    #
    rets = [MY_INF]
    for i in range(M):
        if (state | c_bin[i]) > state:
            rets.append(a[i] + dp((state | c_bin[i])))
    ret = min(rets)
    #
    memo[state] = ret
    return ret

ans = dp(0)
if ans != MY_INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC142_E()

"""

"""

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
from collections import defaultdict
INF = float('inf')
dic = defaultdict(lambda: INF)
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    d = 0
    for k in c:
        d |= (1<<(k-1))
    dic[d] = min(dic[d], a)

dp = [INF] * (1<<N)
dp[0] = 0
for k,v in dic.items():
    for b in range((1<<N)-1):
        if dp[b] == INF: continue
        if b == (b|k): continue
        dp[b|k] = min(dp[b|k], dp[b]+v)
print(-1 if dp[-1]==INF else dp[-1])

Submission status: Accepted

Solution code:
INF = 10**9 + 7


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        A.append(a)
        B.append(b)
        bit = 0
        for s in input().split():
            c = int(s)
            bit |= (1 << (c-1))
        C.append(bit)

    dp = [[INF]*(1 << N) for _ 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])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i][next_bit] = min(dp[i][next_bit], dp[i][j] + A[i])
    ans = dp[M][(1 << N) - 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 2*10**7


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        A.append(a)
        B.append(b)
        bit = 0
        for i in input().split():
            bit |= (1 << (int(i)-1))
        C.append(bit)
    dp = [[INF]*(1 << N) for _ 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])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 2*10**7


def main():
    N, M = (int(i) for i in input().split())
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        A.append(a)
        B.append(b)
        bit = 0
        for i in input().split():
            bit |= (1 << (int(i)-1))
        C.append(bit)
    dp = [[INF]*(1 << N) for _ 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])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  N,M=map(int,input().split())
  A=[0]*M
  import heapq
  import collections
  from itertools import permutations
  table=collections.defaultdict(list)
  AC=[[0,0] for i in range(M)]
  C=[set() for i in range(M)]
  for i in range(M):
    a,b=map(int,input().split())
    AC[i][0]=a
    tmp=set(map(int,input().split()))
    for x in tmp:
      AC[i][1] |= 1<<(x-1)
  dp=[10**9]*(2**N)
  dp[0]=0

  for i in range(1,2**N):
    k=0
    s=set()
    for j in range(1,i):
      if i & j == j:
        dp[i]=min(dp[i],dp[j]+dp[i^j])
    for a,c in AC:
      if c&i == i:
        dp[i]=min(dp[i],a)
    #print(dp[i],bin(i))

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

Submission status: Accepted

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

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

    for _ in range(M):
        price, _ = map(int, input().split())
        c = (int(x) - 1 for x in input().split())
        k = sum(1 << x for x in c)
        for bit in reversed(range(1 << N)):
            nbit = bit | k
            dp[nbit] = min(dp[nbit], dp[bit] + price)

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


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
INF = 2*10**7


def main():
    N, M = (int(i) for i in input().split())
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        A.append(a)
        B.append(b)
        C.append({int(i) for i in input().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):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] != INF:
                next_bit = j
                for bit in C[i]:
                    next_bit |= (1 << (bit-1))
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = list(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())))

A = [10 ** 10] * (1 << N)
C = []
for i in range(M):
  t = 0
  cc = c[i]
  a, b = ab[i]
  for j in cc:
    t |= 1 << (j - 1)
  C.append([t, a])
  A[t] = min(A[t], a)

for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    for j in range(M):
      k, a = n | C[j][0], C[j][1]
      A[k] = min(A[k], A[n] + a)
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

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

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    inf=10**9
    n,m=MI()
    kk=[]
    aa=[]
    for _ in range(m):
        k=0
        a,b=MI()
        aa.append(a)
        cc=LI1()
        for c in cc:k|=1<<c
        kk.append(k)
    dp=[inf]*(1<<n)
    dp[0]=0
    for bit in range(1<<n):
        pre=dp[bit]
        if pre==inf:continue
        for a,k in zip(aa,kk):
            nb=bit|k
            dp[nb]=min(dp[nb],pre+a)
    ans=dp[-1]
    if ans==inf:print(-1)
    else:print(ans)

main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = 2**n
dp = [1000000000 for _ in range(x)]
dp[0] = 0
for i in range(m):
    ai,bi = map(int,input().split())
    c = list(map(int,input().split()))
    bit = 0
    for j in range(bi):
        bit += 2**(c[j]-1)
    for k in range(x):
        dp[k | bit] = min(dp[k | bit],dp[k] + ai)
if dp[x-1] == 1000000000:
    print(-1)
else:
    print(dp[x-1])

Submission status: Accepted

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

n,m = inpl()
wv = []
for i in range(m):
    a,b = inpl()
    cnt = 0
    c = inpl()
    for i in c:
        cnt += 1<<(i-1)
    wv.append((a,cnt))
dp = [INF for _ in range(1<<n)]
dp[0] = 0

for i in range(m):
    v,w = wv[i]
    for j in range(1<<n):
        dp[j|w] = min(dp[j|w], dp[j] + v)
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    g = []
    for _ in range(m):
        a,_ = LI()
        c = LI()
        b = 0
        for i in c:
            b |= 1<<(i-1)
        g.append((b,a))
    B = 1<<n
    dp = [float("inf")]*B
    dp[0] = 0
    for b in range(B):
        for i,v in g:
            nb = b|i
            nd = dp[b]+v
            if nd < dp[nb]:
                dp[nb] = nd
    ans = dp[-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def open(box, key):
    return (box & (2**N-1 - key))
N, M = map(int, input().split())
INF = 10**8+1
dp = [[INF]*2**N for i in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0
key = []
for i in range(M):
    a, b= map(int, input().split())
    n = 0
    c = list(map(int, input().split()))
    for i in range(b):
        n += 2**(c[i]-1)
    key.append((a,n))
for i in range(1,M+1):
    for j in range(2**N):
        dp[i][j] = min(dp[i-1][j], dp[i-1][open(j, key[i-1][1])]+key[i-1][0])
if dp[M-1][2**N-1] == INF:
    dp[M-1][2**N-1] = -1
print(dp[M-1][2**N-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
keys = []
A = [0]*m
for i in range(m):

    a,b=map(int,input().split())
    A[i] = a
    k = 0
    for c in map(int,input().split()):
        k = k| 2**(c-1)
        ## 鍵kがc番目の宝箱を開けられる--> k & 2**(c-1) == 1
    keys.append(k)



dp = [[10**9]*2**n for i in range(m+1)] #dp[i][j] iまで使って状態jを実現する最小コスト
dp[-1][0] = 0
for i in range(m):
    a = A[i]
    k = keys[i]
    for j in range(2**n):
        dp[i][j|k] = min(dp[i-1][j|k],dp[i-1][j]+a,dp[i][j|k])
        ## j|k -->jにkを使って開けられる宝箱の種類
        ## 前のまま(dp[i][j|k]) or jに鍵を使う(dp[i-1][j]+a)
        dp[i][j] = min(dp[i][j],dp[i-1][j]) # 鍵を使わない場合の更新
ans = dp[m-1][2**n-1]
if ans ==10**9:
    print(-1)
else:
    print(ans)