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

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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]]) #i番目を買っているよ
if dp[m-1][-1]==float('inf'):
    print(-1)
else:
    print(dp[m-1][-1])

Submission status: Accepted

Solution code:
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]]) #i番目を買っているよ

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit
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)

Submission status: Accepted

Solution code:
# coding: utf-8

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")

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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
# show_flg = True


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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:


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

dp=[10**8+10]*(2**N)
dp[0]=0
for bi in range(0,2**N):
    for i in range(M):
        t=key[i]
        a,b,c=t
        

        dp[bi|c]=min(dp[bi]+a,dp[bi|c])
if dp[-1]<10**8+10:
    print(int(dp[-1]))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for x, y in zip(can_open, cost):
    for j in range(n_bit):
        m = j | x
        z = dp[j]+y
        if dp[m] > z:
            dp[m] = z

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

Submission status: Accepted

Solution code:
from itertools import product
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j, (x, y) in product(range(n_bit), zip(can_open, cost)):
    m = j | x
    z = dp[j]+y
    if dp[m] > z:
        dp[m] = z

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [[INF]*(m+1) for _ in range(n_bit)]
dp[0][0] = 0

for j in range(n_bit):
    for i in range(m):
        dp[j][i+1] = min(dp[j][i+1], dp[j][i])
        dp[j | can_open[i]][i +
                            1] = min(dp[j | can_open[i]][i+1], dp[j][i+1]+cost[i])

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

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
l=[]
for i in range(m):
  l2=[]
  a,b=map(int,input().split())
  l2.append(a)
  x=list(map(int,input().split()))
  ct=0
  for i in range(n):
    if i+1 in x:
      ct+=2**i
  l2.append(ct)
  l.append(l2)

dp=[[999999999999 for i in range(2**n)] for j in range(m+1)]
dp[0][0]=0
for i in range(1,m+1):
  for j in range(2**n):
    dp[i][j|l[i-1][1]]=min(dp[i-1][j]+l[i-1][0],dp[i][j|l[i-1][1]])
  for j in range(2**n):
    dp[i][j]=min(dp[i][j],dp[i-1][j])

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

Submission status: Accepted

Solution code:
def main():
    import numpy as np

    n, m = map(int, input().split())
    dp = np.full(2**n, 10**9, dtype=np.int64)
    dp[0] = 0
    opened = np.arange(2**n)

    for _ in range(m):
        cost, types = map(int, input().split())
        to_open = np.array(list(map(int, input().split())), dtype=np.int64)

        openable = np.left_shift(1, to_open-1).sum()
        new_indexes = opened | openable
        new_costs = dp + cost
        sort_index = np.argsort(new_costs)
        new_costs.sort()
        update_pattern, idx = np.unique(new_indexes[sort_index], return_index=True)
        update_cost = new_costs[idx]
        dp[update_pattern] = np.minimum(dp[update_pattern], update_cost)

    full_open = 2**n - 1
    ans = dp[full_open]
    if ans == 10 ** 9:
        ans = -1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    DP = [10**9] * 2**n
    DP[0] = 0
    updated_patterns = {0}
    for _ in range(m):
        cost, types = map(int, input().split())
        to_open = list(map(int, input().split()))

        openable = 0
        for open in to_open:
            openable += 1 << (open-1)
        new_updated = set()
        for opened in updated_patterns:
            pattern = opened | openable
            new_cost = DP[opened] + cost
            if DP[pattern] > new_cost:
                DP[pattern] = new_cost
                new_updated.add(pattern)

        updated_patterns |= new_updated

    full_open = 2**n - 1
    ans = DP[full_open]
    if ans == 10 ** 9:
        ans = -1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    all_patterns = 2**n
    DP = [10**9] * all_patterns
    DP[0] = 0
    for _ in range(m):
        cost, types = map(int, input().split())
        to_open = list(map(int, input().split()))

        openable = 0
        for open in to_open:
            openable += 1 << (open-1)

        for opened in range(all_patterns):
            pattern = opened | openable
            new_cost = DP[opened] + cost
            if DP[pattern] > new_cost:
                DP[pattern] = new_cost

    full_open = 2**n - 1
    ans = DP[full_open]
    if ans == 10 ** 9:
        ans = -1
        
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

DP = [10**9] * (2**n)
DP[0] = 0
for _ in range(m):
    cost, types = map(int, input().split())
    to_open = list(map(int, input().split()))

    openable = 0
    for open in to_open:
        openable += 1 << (open-1)

    for opened in range(2 ** n):
        pattern = opened | openable
        DP[pattern] = min(DP[pattern], DP[opened] + cost)

full_open = 2**n - 1
ans = DP[full_open]

if ans == 10 ** 9:
    ans = -1

print(ans)

Submission status: Accepted

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

for _ in range(m):
    cost, types = map(int, input().split())
    to_open = list(map(int, input().split()))
    keys.append([cost, to_open])

DP = [10**9] * (2**n)
DP[0] = 0

for cost, (to_open) in keys:
    openable = 0
    for open in to_open:
        openable |= 1 << (open-1)

    for opened in range(2 ** n):
        pattern = opened | openable
        DP[pattern] = min(DP[pattern], DP[opened] + cost)

full_open = 2**n - 1
ans = DP[full_open]

if ans == 10 ** 9:
    ans = -1

print(ans)

Submission status: Accepted

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

dp=[10**9]*(1<<n)
dp[0]=0
for _ in range(m):
    a,b=map(int,input().split())
    key=0
    for i in map(int,input().split()):
        key+=1<<(i-1)
    for i in range(1<<n):
        dp[i|key]=min(dp[i|key],dp[i]+a)
if dp[-1]>10**8:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

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

def conv_to_bit(clist):
  ret=0
  for c in clist:
    ret+=2**(c-1)
  return ret

alist=[]
cmat=[]
for i in range(M):
  a,b=map(int,input().split())
  alist.append(a)
  clist=list(map(int,input().split()))
  cmat.append(clist)
  
dp=[]
for i in range(M+1):
  dp.append([float("inf")]*(2**N))
dp[0][0]=0
  
for i in range(M):
  cbit=conv_to_bit(cmat[i])
  for j in range(2**N):
    dp[i+1][j]=dp[i][j]

  for j in range(2**N):
    bit_or=j|cbit
    dp[i+1][bit_or]=min(dp[i+1][bit_or],dp[i][j]+alist[i])
    
if dp[-1][-1]==float("inf"):
  print(-1)
else:
  print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
    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
    import math

    inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    # key[i]:10進数でiを開けれる鍵の値段
    key = []
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        key.append((binary, a))

    # dp[i]:10進数で宝iを開けてる時の最小値段
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i, a in key:
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+a)
    print(dp[-1] if dp[-1] != inf else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    # key[i]:10進数でiを開けれる鍵の値段
    key = [inf]*(1<<n)
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        if key[binary] > a:
            key[binary] = a

    # dp[i]:10進数で宝iを開けてる時の最小値段
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        if key[i] == inf:
            continue
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+key[i])
    print(dp[-1] if dp[-1] != inf else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    # key[i]:10進数でiを開けれる鍵の値段
    key = [inf]*(1<<n)
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        if key[binary] > a:
            key[binary] = a

    # dp[i]:10進数で宝iを開けてる時の最小値段
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        if key[i] == inf:
            continue
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+key[i])
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    # key[i]:10進数でiを開けれる鍵の値段
    key = []
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        key.append((binary, a))

    # dp[i]:10進数で宝iを開けてる時の最小値段
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i, a in key:
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    # key[i]:10進数でiを開けれる鍵の値段
    key = [inf]*(1<<n)
    for _ in range(m):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        binary = 0
        for i in c:
            binary += 2**(i-1)
        key[binary] = min(key[binary], a)

    # dp[i]:10進数で宝iを開けてる時の最小値段
    dp = [inf]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        if key[i] == inf:
            continue
        for s in range(1<<n):
            if (i|s) == s:
                continue
            dp[i|s] = min(dp[i|s], dp[s]+key[i])
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

n,m = map(int,stdin.readline().rstrip().split())
c = []
a_list = []

def main():
    for i in range(m):
        a,b = map(int,stdin.readline().rstrip().split())
        a_list.append(a)
        c.append(sum(1 << j-1 for j in list(map(int,stdin.readline().rstrip().split()))))

    inf = 10**10
    dp = [inf]*(1 << n)
    dp[0] = 0

    for i in range(1 << n):
        for A,C in zip(a_list,c):
            dp[C|i] = min(dp[C|i],dp[i]+A)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
	N, M = MAP()
	dp = [INF]*(1<<N)
	dp[0] = 0

	for _ in range(M):
		a, b = MAP()
		c = LIST()
		tmp = 0
		for x in c:
			tmp = tmp|1<<(x-1)
		for S in range(1<<N):
			dp[S|tmp] = min(dp[S|tmp], dp[S]+a)

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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N, M = map(int, input().split())
INF = 10**12
AB = []
C = []
for i in range(M):
    AB.append(tuple(int(x) for x in input().split()))
    C.append(sum(1<<(int(x)-1) for x in input().split()))

dp = [INF]*(1<<N)
dp[0] = 0
for i in range(1<<N):
    for (a, b), c in zip(AB, C):
        m = i | c
        dp[m] = min(dp[m], dp[i]+a)
        
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
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())))
dp = [[10**18] * (2 ** n) for i in range(m+1)]
dp[0][0] = 0
for i,((a,b),c) in enumerate(zip(ab,c)):
  d = 0
  for x in c:
    d += 2 ** (x-1)
  for j in range(2**n):
    NEXT = j | d
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][NEXT] = min(dp[i+1][NEXT], dp[i][j]+a)
ans = dp[m][2**n-1]
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)

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])
  bit=0
  for i in input().split():
    bit|=(1<<(int(i)-1))
  c.append(bit)
inf=float("inf")
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])
    next_bit=j|c[i]
    dp[i+1][next_bit]=min(dp[i+1][next_bit],dp[i][j]+a[i])
print(dp[-1][-1] if dp[-1][-1]!=inf else -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[i]: 状態がbin(i)の時のの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けることが可能
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:
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()))
        bit = ["0"] * n
        for c in C:
            bit[c - 1] = "1"

        bit = "".join(bit)
        ABC.append([a, b, int(bit, 2)])

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

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


if __name__ == '__main__':
    resolve()