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:
N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    t = 0
    for j in c:
        t |= 1 << (j - 1)  # 1:1, 2:10, 3:100, 4:1000,…
    key.append([t, a])  # 開けられる宝箱を2進数で保持

INF = 10 ** 12
dp = [INF] * (1 << N)  # 1 << N : 2 ** N
dp[0] = 0  # 初期設定
for i in range(1 << N):
    for j in range(M):
        T = i | key[j][0]  # i:すでに開けられる宝箱の状態と鍵で開けられる宝箱の和集合
        cost = dp[i] + key[j][1]
        dp[T] = min(dp[T], cost)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
b_cnt = 2 ** N #箱の数は最大12個
INF = 10 ** 9
dp = [INF] * b_cnt
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (int(x)-1) for x in list(input().split())])
    for j in range(b_cnt):
        if dp[j|c] > dp[j] + a:
            dp[j|c] = dp[j] + a

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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    b_cnt = 2 ** N #箱の数は最大12個
    INF = 10 ** 9
    dp = [INF] * b_cnt
    dp[0] = 0

    for i in range(M):
        a, b = map(int, input().split())
        c = sum([2 ** (int(x)-1) for x in list(input().split())])
        for j in range(b_cnt):
            if dp[j|c] > dp[j] + a:
                dp[j|c] = dp[j] + a

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = []
for i in range(m):
    a,b = map(int,input().split())
    c = 0
    for j in map(int,input().split()):
        c += (1<<(j-1))
    l.append((c,a))
dp = {0:0}
for i in l:
    items = list(dp.items())
    for j in items:
        ij = (i[0] | j[0], i[1] + j[1])
        if not dp.get(ij[0]):
            dp[ij[0]] = ij[1]
        else:
            if dp[ij[0]] > ij[1]:
                dp[ij[0]] = ij[1]

print(dp.get(2**n-1,-1))

Submission status: Accepted

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

n, m = map(int, input().split())

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

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(i-1) for i in map(int, input().split())])
    for i in range(p):
        if dp[i|c] > dp[i] + a: 
            dp[i|c] = dp[i] + a
    
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    keys = []
    for _ in range(M):
        a, _ = map(int, input().split())
        c = 0
        for i in list(map(int, input().split())):
            c += (1 << (i-1))
        keys.append((a, c))

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

    for i, (a, c) in enumerate(keys):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][j | c] = min(dp[i+1][j | c], dp[i][j] + a)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
  n, m = map(int, input().split())
  p = 2 ** n
  inf = 10 ** 9
  dp = [inf] * p
  dp[0] = 0

  for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(j)-1) for j in list(input().split())])
    for k in range(p):

        ## 同じ状態を再現するのにより多くのお金を使っていた場合
      if dp[k|c] > dp[k] + a:
        dp[k|c] = dp[k] + a

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

n,m = map(int,input().split())
A = []
B = []
C = []
for i in range(m):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    c_list = list(map(int,input().split()))
    c = 0
    for j in range(B[i]):
        c += 2**(c_list[j]-1)
    C.append(c)

dp = [[10**9]*(2**n) for _ in range(m+1)]
dp[0][0] = 0

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

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
 
dic = {0:0}
 
for i in range(m):
  a,b = map(int,input().split())
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    if (k|c) in dic2.keys():
      dic2[k|c] = min(dic2[k|c],a+v)
    else:
      dic2[k|c] = a+v
 
  dic = dic2
 
if ((2**n)-1) in dic.keys():
  print(dic[(2**n) -1])
else:
  print(-1)

Submission status: Accepted

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

a_list = []
c_list = []

for i in range(M):
    a,b = list(map(int,input().split()))
    a_list.append(a)
    c = list(map(int,input().split()))
    d = 0
    for cc in c:
        d += 2**(cc-1)
    c_list.append(d)

DP = [[10**27]*(2**N) for i in range(M+1)]
DP[0][0]=0
for i in range(1,M+1):
    for j in range(2**N):
        #print(c_list[i-1] | j)
        DP[i][j] = min(DP[i][j],DP[i-1][j])
        DP[i][c_list[i-1] | j] = min(DP[i][c_list[i-1] | j],DP[i-1][j] + a_list[i-1])

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

Submission status: Accepted

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

l=[]
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  l.append([s,a])

v=[10**7 for x in range(2**n)]
v[0]=0
for s,a in l:
  for j in range(2**n):
    if v[j] != 10**7:
      v[j|s] = min(v[j|s], v[j]+a)

print(v[2**n-1] if v[2**n-1] != 10**7 else -1)

Submission status: Accepted

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

f=[10**7 for x in range(2**n)]
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  f[s]=min(f[s],a)

l=[]
for i in range(2**n):
  if f[i] != 10**7:
    l.append([i,f[i]])

v=[10**7 for x in range(2**n)]
v[0]=0

for s,a in l:
  for j in range(2**n):
    if v[j] != 10**7:
      v[j|s] = min(v[j|s], v[j]+a)

print(v[2**n-1] if v[2**n-1] != 10**7 else -1)

Submission status: Accepted

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

l = []

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    bit_c = 0
    for x in c:
        bit_c = bit_c | (1<<(x-1))
    l.append([a,bit_c])

dp = [[float("INF")]*(2**n+1) for _ in range(m+1)]

dp[1][0] = 0
dp[1][l[0][1]] = l[0][0]

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

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

Submission status: Accepted

Solution code:
import sys


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    s = 0
    for j in range(b):
        s |= 1<<(c[j]-1)
    key.append([s, a])

INF = 10**8
dp = [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 == INF:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import reduce


def solve(*args: str) -> str:
    a_max = 1+12*10**5
    n, m = map(int, args[0].split())
    cache = {}

    for i in range(1, 1+2*m, 2):
        a, _ = map(int, args[i].split())
        c = reduce(
            lambda x, y: x | 1 << y-1,
            [0] + list(map(int, args[i+1].split()))
        )
        cache[c] = min(cache.get(c, a_max), a)

    for C in tuple(cache.items()):
        unlocked, cost = C
        for E in tuple(cache.items()):
            c, a = E
            cache[unlocked | c] = min(
                cache.get(unlocked | c, a_max),
                a + cost
            )

    return str(cache.get(2**n-1, -1))


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Submission status: Accepted

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

for _ in range(M):
    cost, _ = map(int, input().split())
    mask = 0
    for i in map(int, input().split()):
        mask |= (1 << (i - 1))
    keys.append((cost, mask))

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

for i, (cost, mask) in enumerate(keys, start=1):
    for state in range(1 << N):
        dp[i][state] = min(dp[i - 1][state], dp[i][state])
        dp[i][state | mask] = min(dp[i - 1][state] + cost, dp[i][state | mask])

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

Submission status: Accepted

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

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

  
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    pw = 2 ** n
    dp = [10 ** 20] * pw
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        c = sum(2 ** (i - 1) for i in list(map(int, input().rstrip('\n').split())))
        for j in range(pw):
            if dp[j | c] > dp[j] + a:
                dp[j | c] = dp[j] + a
    if dp[-1] == 10 ** 20:
        print(-1)
    else:
        print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    tc = list(map(int, input().split()))
    c.append(tc)
p = 2**n
dp = [float('inf')] * p
dp[0] = 0

for i in range(m):
    for j in range(p):
        t = p-1
        for cc in c[i]:
            t -= (1 << (cc-1))
        for cc in c[i]:
            if j >> (cc-1) & 1:
                dp[j] = min(dp[j], dp[j&t] + a[i])
if dp[p-1] == float('inf'):
    print(-1)
else:
    print(dp[p-1])

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
a = [0]*M; b = [0]*M; c = [0]*(M)
for i in range(M):
    a[i], b[i] = LI()
    C = LI()
    for j in range(b[i]):
        c[i] += 2**(C[j]-1)
cou = int(0)
#print(c)
dp = [[0]*(2**N) for _ in range(N)]
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for k in range(M):
        if i^c[k]!=i-c[k]:
            dp[i|c[k]] = min(dp[i|c[k]],dp[i]+a[k])

ans = dp[2**N-1]
if ans==inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
INF = 10**9
dic = [0]*(M+1)
bit = 0
for i in range(M):
  a, b = map(int, input().split())
  c = [int(x) for x in input().split()]
  j = 0
  s = 0
  for n in range(N):
    if n==c[j]-1:
      s += 2**n
      j += 1 if j<len(c)-1 else 0
    else:
      s += 0
  bit |= s
  dic[i+1] = (a,s)
if bit!=(1<<N)-1:
  print(-1)
else:
  dp = [INF]*(1<<N)
  dp[0] = 0
  for i in range(1,M+1):
    a, s = dic[i]
    for j in range(1<<N):
      dp[j|s] = min(dp[j]+a, dp[j|s])
  print(dp[-1])

Submission status: Accepted

Solution code:
def p_e():
    N, M = map(int, input().split())
    max_value = (10 ** 5) * 12 + 1
    dp_len = 2 ** N
    dp = [max_value] * dp_len
    dp[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        keys = list(map(int, input().split()))
        index = 0
        for key in keys:
            index += 2 ** (key - 1)

        for i in range(dp_len):
            if dp[i] == max_value:
                continue
            dp_index = i | index
            dp[dp_index] = min(dp[dp_index], dp[i] + a)

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


if __name__ == '__main__':
    p_e()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# coding: utf-8
# 

from itertools import *
import sys


#################### library ####################


#################### naive ####################


#################### process ####################

def read_input():
	[N, M] = map(int, raw_input().split())
	v = []
	for k in range(M):
		a, b = map(int, raw_input().split())
		cs = [ int(e) for e in raw_input().split() ]
		flag = reduce(lambda x, y: x | (1 << (y-1)), cs, 0)
		v.append((a, flag))
	return (N, v)

def proc():
	N, v = read_input()
	
	L = 1 << N
	memo = [10**9] * L
	memo[0] = 0
	for n in range(L-1):
		for a, flag in v:
			n1 = n|flag
			memo[n1] = min(memo[n1], memo[n] + a)
	
	if memo[L-1] == 10**9:
		return -1
	else:
		return memo[L-1]


#################### main ####################

print proc()

Submission status: Accepted

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

DP = [[10**9]*(2**N) for i in range(M+1)]
DP[0][0] = 0
key = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    d = 0
    for j in c:
        d += 2**(j-1)
    key.append([a,d])
for i in range(M):
    cost,p = key[i]
    for j in range(2**N):
        q = j - (p&j)
        DP[i+1][j] = min(DP[i][j],cost+DP[i][q])
ans = DP[-1][-1]
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    INF = float('inf')
    
    L = 2 ** N
    dp = [INF] * L
    dp_next = [INF] * L
    
    nums = [2 ** i for i in range(N)]
    
    for i in range(M):
        a, b = map(int, input().split())
        b = sum([nums[c-1] for c in list(map(int, input().split()))])            
    
        dp[b] = min(dp[b], a)
        for j in range(L):
            n = j | b
            dp_next[n] = min(dp[n], dp_next[n], dp[j]+a)
        
        for j in range(L):
            dp[j] = dp_next[j]
            
    if dp[-1] == INF: print(-1)
    else: print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n,m = words(int)

dp = [-1] * (2**n)
dp[0] = 0

def to_bits(xs):
    bits = 0
    for x in xs:
        bits += 2**(x-1)
    return bits

costs = []
bits = []
for i in range(m):
    c,k = words(int)
    costs.append(c)
    ys = words(int)
    bits.append(to_bits(ys))

#print(costs)
#print(bits)

for cur in range(2**n):
    if dp[cur] == -1:
        continue
    #print(dp)
    for c,b in zip(costs, bits):
        next = cur | b
        if dp[next] == -1 or dp[next] > dp[cur] + c:
            dp[next] = dp[cur] + c

print(dp[2**n-1])

Submission status: Accepted

Solution code:
def main():
    N,M = map(int, input().split())
    inf = 10**9
    p = 2**N
    dp = [inf] * p
    dp[0] = 0
    
    for i in range(M):
        a,b = map(int, input().split())
        c = sum([2**(int(j)-1) for j in list(input().split())])
        for k in range(p):
            if dp[k|c] > dp[k] + a:
                dp[k|c] = dp[k] + a
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
inf = 10 ** 18
cost = [inf for _ in range(2**n)]
cost[0] = 0
for _ in range(m):
  a,b = map(int,input().split())
  c = list(map(int,input().split()))
  key = 0
  for i in range(b):
    key += 2 ** (c[i]-1)
  #print(key)
  for t in range(2**n):
    cost[t|key] = min(cost[t|key],cost[t]+a)
#print(cost)
ans = cost[-1]
if ans < inf:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def binize(vn):
    res = 0
    for n in vn:
        res |= 1 << (n-1)
    return res


N, M = map(int, input().split())
mK = []
for i in range(M):
    a, b = map(int, input().split())
    vc = list(map(int, input().split()))
    mK.append((a, binize(vc)))

# 2**N up to 4096
allOpen = 2**N - 1
INF = float("inf")

# dp[i:keyM(<=1000)][n:openedN(<4096)] := min(sum(a))
dp = []
dp.append([0,]+[INF,]*allOpen)

#print(dp)
for na,n in mK:
	nDP = dp[-1]
	for c,pa in enumerate(dp[-1]):
		nDP[n|c] = min(nDP[n|c], pa+na)
	dp.append(nDP)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 1e9
dp = [inf] * (1 << n)
dp[0] = 0

for _ in range(m):
  a, b = map(int, input().split())
  cs = list(map(int, input().split()))
  r = 0
  for c in cs:
    r |= 1 << (c - 1)
  for i in range(1 << n):
    if dp[i | r] > dp[i] + a:
      dp[i | r] = dp[i] + a
      
if dp[(1 << n) - 1] == inf:
  print("-1")
else:
  print("{}".format(dp[(1 << n) - 1]))

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 permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

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()))
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()
		d = 0
		for x in c:
			d += 1<<(x-1)

		for j in range(1<<N):
			tmp = j|d
			dp[tmp] = min(dp[tmp], dp[j]+a)

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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
MAX_INT = int(10e10)

N, M = list(map(int,input().split()))
Val = [0 for _ in range(M)]
Key = [0 for _ in range(M)]
for i in range(M):
  v, b = list(map(int,input().split()))
  k =  list(map(int,input().split()))
  Val[i] = v
  tmp = 0
  for num in k:
    tmp += 2**(num-1)
  Key[i] = tmp
#print(Val)
#print(Key)

dp = [MAX_INT for _ in range(1<<N)]
dp[0] = 0
for i in range(1<<N):
  for x in range(M):
    #print(i, i|Key[x])
    dp[i|Key[x]] = min(dp[i|Key[x]], dp[i] + Val[x])
#print(dp)
if dp[-1] == MAX_INT:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

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

N,M=map(int,input().split())
L=[]
PL=[2**x for x in range(N)]
for i in range(M):
    cost,_=map(int,input().split())
    k=sum([PL[i-1] for i in map(int,input().split())])
    L.append((cost, k))

p=2**N
dp=[10**7]*p
dp[0]=0
for i in range(M):
    cost, k=L[i]
    for j in range(p):
        m=j|k
        dp[m]=min(dp[m],dp[j]+cost)
print(dp[-1] if dp[-1]<10**7 else -1)

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    n, m = map(int, input().split())

    size = (1 << n)

    dp = [inf] * size
    dp[0] = 0

    for _ in range(m):
        price, _ = map(int, input().split())
        key = sum(1 << ind for ind in (int(x) - 1 for x in input().split()))
        for mask in range(size):
            if dp[mask] == inf:
                continue
            n_mask = (mask | key)
            dp[n_mask] = min(dp[n_mask], dp[mask] + price)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    n, m = map(int, input().split())

    size = (1 << n)

    dp = [inf] * size
    dp[0] = 0

    for _ in range(m):
        price, _ = map(int, input().split())
        key = sum(1 << ind for ind in (int(x) - 1 for x in input().split()))
        for mask in range(size):
            dp[mask | key] = min(dp[mask | key], dp[mask] + price)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
inf = 10 ** 8 + 10

n, m = map(int, input().split())

keys = set()

for i in range(m):
    price, _ = map(int, input().split())
    key = 0
    for ind in (int(x) - 1 for x in input().split()):
        key += (1 << ind)
    keys.add((price, key))

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

for price, key in sorted(keys):
    for mask in range(1 << n):
        dp[mask | key] = min(dp[mask | key], dp[mask] + price)

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

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    INF = 10 ** 10
    p = 2 ** N
    dp = [INF] * p
    dp[0] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        c = sum([2 ** (i - 1) for i in map(int, input().split())])
        for i in range(p):
            if dp[i | c] > dp[i] + a:
                dp[i | c] = dp[i] + a

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    INF = 10 ** 10
    p = 2 ** N
    dp = [INF] * p
    dp[0] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        c = sum([2 ** (i - 1) for i in map(int, input().split())])
        for i in range(p):
            dp[i | c] = min(dp[i] + a, dp[i | c])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, M = map(int, input().split())
INF = 10 ** 10
p = 2 ** N
dp = [INF] * p
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (i - 1) for i in map(int, input().split())])
    for i in range(p):
        dp[i | c] = min(dp[i] + a, dp[i | c])

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0] * M # 鍵の値段
c = [[]] * M
INF = 100000001
dp = [INF for i in range(2 ** N)]
for i in range(M):
    a[i], _ = map(int, input().split())
    c[i] = list(map(int, input().split()))

b = []
for l in c:
    g = 0
    for n in l:
        g |= 1 << (n - 1)
    b.append(g)
l = 2 ** N
dp[0] = 0
for s in range(l):
    for i in range(M):
        p = s | b[i]#i番目の鍵に対応したbit数列
        dp[p] = min(dp[p], dp[s] + a[i])

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

Submission status: Accepted

Solution code:
def main():
  Inf = 10**8
  N, M = list(map(int, input().split(" ")))
  keys = []
  for _ in range(M):
      c = list(map(int, input().split(" ")))
      j = list(map(int, input().split(" ")))
      keys.append([c[0], sum([1 << k-1 for k in j])])
  dp = [Inf for _ in range(1 << N)]
  dp[0] = 0
  for i in range(len(dp)):
      for key in keys:
          t = i | key[1]
          dp[t] = min(dp[t], key[0] + dp[i])
  if dp[-1]==Inf:
      print(-1)
  else:
      print(dp[-1])
main()

Submission status: Accepted

Solution code:
def main():
  N,M=map(int,input().split())
  Inf=10**8
  dp=[Inf]*(2**N)
  dp[0]=0
  for i in range(M):
    a,b=map(int,input().split())
    tmp=list(map(int,input().split()))
    open_tresure=list(1<<j-1 for j in tmp)
   # print(open_tresure)
    op_tr=sum(open_tresure)
    for j in range(2**N):
      key=op_tr | j
      dp[key]=min(dp[key],dp[j]+a)
  if dp[-1]==Inf:
    print(-1)
  else:
    print(dp[-1])

main()

Submission status: Accepted

Solution code:
def main():
  N,M=map(int,input().split())
  Inf=10**8
  dp=[Inf]*(2**N)
  dp[0]=0
  for i in range(M):
    a,b=map(int,input().split())
    tmp=list(map(int,input().split()))
    open_tresure=list(1<<j-1 for j in tmp)
   # print(open_tresure)
    op_tr=sum(open_tresure)
    for j in range(2**N):
      key=op_tr | j
      dp[key]=min(dp[key],dp[j]+a)
  if dp[-1]==Inf:
    print(-1)
  else:
    print(dp[-1])

main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Inf = 10**8
Dp = [Inf]*(2**N)
Dp[0] = 0

for i in range(M): #カギiで
    a,_=map(int, input().split())
    d = sum((1<<p-1) for p in list(map(int, input().split()))) #iで開けられる宝箱の2bit表記
    for j in range(2**N):
        ope = j|d
        Dp[ope] = min(Dp[ope], Dp[j] + a)

if Dp[-1] == Inf:
    print(-1)
else:
    print(Dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Inf = 10**8
Dp = [Inf]*(2**N)
Dp[0] = 0

for i in range(M): #カギiで
    a,_=map(int, input().split())
    c = list(map(int, input().split()))
    d = sum((1<<p-1) for p in c) #iで開けられる宝箱の2bit表記
    for j in range(2**N):
        ope = j|d
        Dp[ope] = min(Dp[ope], Dp[j] + a)

if Dp[-1] == Inf:
    print(-1)
else:
    print(Dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a, b, c = [], [], []
for _ in range(M):
    a_, b_ = map(int, input().split())
    c_ = list( map(int, input().split()) )
    a.append(a_)
    b.append(b_)
    c.append(c_)

INF = 10**9
bit_dp = [INF for _ in range(2**N)]
bit_dp[0] = 0
for i in range(M):
    bit_n = 0
    for j in c[i]:
        bit_n |=  1 << j - 1
    for j in range(2**N):
        if bit_dp[j|bit_n] > bit_dp[j] + a[i]:
            bit_dp[j|bit_n] = bit_dp[j] + a[i]

res = -1 if bit_dp[-1] >= INF else bit_dp[-1]
print(res)

Submission status: Accepted

Solution code:

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

C = [float('inf')] * (1 << N)
C[0] = 0
key_v = [float('inf')] * (1 << N)
for j in range(M):
    a, b = map(int, input().split())
    box = list(map(int, input().split()))
    ex_status = 0
    for j in box:
        ex_status += 1 << (j-1)
    key_v[ex_status] = min(a, key_v[ex_status])

for key, val in enumerate(key_v):
    if val == float('inf'):
        continue
    for i in range(1 << N):
        now_status = i
        score = C[now_status] + val
        if score == float("inf"):
            continue

        now_status = i | key

        if C[now_status] > score:
            C[now_status] = score

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(N, M, A, B, C):
    key = []  # type: "List[List[int, int]]"
    for i in range(M):
        s = 0
        for j in range(B[i]):
            s |= 1 << (C[i][j] - 1)
        key.append([s, A[i]])
    
    INF = 1001001001
    dp = [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]
    print(-1 if ans == INF else ans)
    pass


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A, B, C = [], [], []
    for _  in range(M):
        A.append(int(next(tokens)))
        B.append(int(next(tokens)))
        C.append([int(next(tokens)) for _ in range(B[-1])])
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()