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: Runtime Error

Solution code:
from bisect import *
N,M=map(int,input().split())
kagi=[]
for i in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for i in range(b):
        C[i]-=1
    kagi.append([a,set(C)])

value=10**7
idx=-1
for i in range(M):
    if 0 in kagi[i][1] and kagi[i][0]<value:
        value=kagi[i][0]
        idx=i
if idx==-1:
    print(-1)
    exit()
kagilst=[idx]

takara=[set() for i in range(N)]
for m in range(M):
    for k in kagi[m][1]:
        takara[k].add(m)

for n in range(1,N):
    if [k for k in kagilst if n in kagi[k][1]]:
        continue
    tempvalue=10**7
    for k in takara[n]:
        lst=[0 for i in range(n)]
        for z in kagilst+[k]:
            for m in kagi[z][1]:
                if m<len(lst):
                    lst[m]=1
        for i in range(len(kagilst)**2):
            A=bin(i)[:2]
            A=list(reversed(list(A)))
            for a in range(len(kagilst)):
                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        lst[h]=1
            if not 0 in lst:
                temptempvalue=value+sum([kagi[a][0] for a in range(len(kagilst)) if A[a]=="1"])+kagi[k][0]
                if temptempvalue<tempvalue:
                    tempvalue=temptempvalue
                    tempkagi=k
    if tempvalue==10**7:
        print(-1)
        exit()
    value=tempvalue
    kagilst.append(k)
print(value)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[0]*M
import collections
table=collections.defaultdict(list)
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  A[i]=a
  c=list(map(int,input().split()))
  C[i]=set(c)
  for x in c:
    table[x].append((a,i))

opened=set()
used=set()
for i in range(1,N+1):
  if used & C[i]:
    opened.add(i)
    continue
  table[i].sort(key=lambda x:x[0])
  used.add(table[i][0][1])
  opened.add(i)
ans=0
for x in used:
  ans+=A[x]
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [[]]
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a)
ans = 0
n = 0
while n < ((N-1)*N)//2:
    f = []
    ans += 1
    t = 0
    for i in range(1,N+1):
        if i in f:
            continue
        if len(A[i]) > 0:
            a = A[i][0]
        else:
            continue
        if (A[a][0] == i):
            if a not in f:
                A[i].pop(0)
                A[a].pop(0)
                f.append(i)
                f.append(a)
                n += 1
                t = 1
    if t == 0:
        print(-1)
        quit()
print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

def saiki(m,box,ans):
    if m==M:
        if sum(box)==len(box):
            return ans
        else:
            return 10**18
    else:
        open=box[:]
        for item in l[m][1]:
            open[item]=1
        return min(saiki(m+1,box,ans),saiki(m+1,open,ans+l[m][0]))


l=[]
for _ in range(M):
    a,b=map(int,input().split())
    temp=list(map(lambda x: int(x)-1,input().split()))
    l.append([a,temp])

ans=saiki(0,[0]*N,0)

print(ans if ans!=10**18 else -1)

Submission status: Runtime Error

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

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

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

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

print(dp(0, 0))

Submission status: Runtime Error

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

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

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

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

print(dp(0, 0))

Submission status: Runtime Error

Solution code:
import copy
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
lv=[]
lk=[]
for i in range(m):
  a,b=map(int,input().split())
  l=list(map(int,input().split()))
  lv.append(a)
  lk.append(l)
ans=[10**10]
def dfs(now,d,price):#どの鍵を採用していくか？
  b=True
  for i in d:
    if d[i]==0:
      b=False
  if b:
    ans[0]=min(ans[0],price)
    return
  if now==n:
    return
  dk=lk[now]
  b=False
  for i in dk:
    if d[i]==0:
      b=True
  if not b:
    dfs(now+1,d,price)
  else:
    dfs(now+1,d,price)
    d1=copy.deepcopy(d)
    for i in dk:
      d1[i]=1
    dfs(now+1,d1,price+lv[now])
d={}
for i in range(1,n+1):
  d[i]=0
dfs(0,d,0)
print(ans[0])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from itertools import product, permutations, combinations
from time import time

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

q = list(range(N))
c = defaultdict(int)
t = [0]*N
r = 0
a = time()

while q:
    b = time()
    if b - a > 0.9:
        print(N*(N-1)//2)
        exit()
    r += 1
    nq = []
    for i in q:
        j = A[i][t[i]] - 1
        k = i
        if k < j:
            j, k = k, j
        c[(j, k)] += 1
        if c[(j, k)] == 2:
            t[j] += 1
            t[k] += 1
            if t[j] < N-1:
                nq.append(j)
            if t[k] < N-1:
                nq.append(k) 
    q = nq

for tt in t:
    if tt != N-1:
        print(-1)
        exit()

print(r)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
INF = 1001001001
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):
        c[j] -= 1
        s |= 1 << c[j]
    key.append([s, a])

dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        print(dp)
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
print(ans)

Submission status: Runtime Error

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

import collcetions
allstate = (1 << N) - 1
dp = collections.defaultdict(lambda:float('inf'))
dp[0] = 0
 
for cost, key_set in keys:
    ndp = dp.copy()
    for state, val in dp.items():
        ndp[state|key_set] = min(ndp[state|key_set], val + cost)
    dp = ndp
if allstate in dp:
    print(dp[allstate])
else:
    print(-1)

Submission status: Runtime Error

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


allstate = (1 << N) - 1
dp = [float('inf')] * (1<<N)
dp[0] = 0

for cost, key_set in keys.items():
    for state in range(1<<N):
        if dp[state] == float('inf'): continue
        nstate = state | key_set
        dp[nstate] = min(dp[nstate], dp[state] + cost)

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

Submission status: Runtime Error

Solution code:
from collections import deque
n , m = map(int, input().split())
keys = deque()
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = deque(list(map(int, input().split())))
    keys.append(deque([a]) + c)
inf = 10 ** 8
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i-1].popleft()
    can_open = keys[i-1]
    for j in range(2**n):
        next = j | trans(can_open)
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Runtime Error

Solution code:
# 鍵の種類は12だからdfs で行けそう
N, M = map(int, input().split())
A = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    A.append(a)
    C.append(c)

def dfs(i, sum, box):
    global answer
    if i == M:
        if len(box) == N:
            answer = min(answer, sum)
    else:
        dfs(i+1, sum, box)
        dfs(i+1, sum+A[i], box|C[i])

INF = 10 ** 7
answer = INF
box = set()
dfs(0, 0, box)
#print(A)
#print(C)
if answer == INF:
    print(-1)
else:
    print(answer)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
 
dic = {0:0}
 
for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  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: Runtime Error

Solution code:
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic = {0:0}
 
 
for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  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_arr.append(int(''.join(arr),2))
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    if (k|c) in dic.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: Runtime Error

Solution code:
import sys
 
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic_arr = [{i:sys.maxsize for i in range(2 ** n)}]
dic_arr[0][0] = 0
 
for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for i in range(1, n+1):
    if i in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i].items():
    dic_arr[i+1][k|c] = min(dic_arr[i+1][k|c],a+v)  
 
if dic_arr[m][(2**n)-1] != sys.maxsize:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys

n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []

dic_arr = [{}]
dic_arr[0][0] = 0

for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for i in range(1, n+1):
    if i in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c_arr.append(int(''.join(arr),2))

for i in range(m):
  a = a_arr[i]
  b = b_arr[i]
  c = c_arr[i]
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i+1].items():
    if (k|c) in dic_arr[i].keys():
      dic_arr[i+1][k|c] = min(dic_arr[i][k|c],a+v)
    else:
      dic_arr[i+1][k|c] = a+v

if ((2**n)-1) in dic_arr[m]:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys

n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []

dic_arr = [{}]
dic_arr[0][0] = 0

for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for i in range(1, n+1):
    if i in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c_arr.append(int(''.join(arr),2))

for i in range(m):
  a = a_arr[i]
  b = b_arr[i]
  c = c_arr[i]
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i].items():
    if (k|c) in dic_arr[i].keys():
      dic_arr[i+1][k|c] = min(dic_arr[i][k|c],a+v)
    else:
      dic_arr[i+1][k|c] = a+v

if ((2**n)-1) in dic_arr[m]:
  print(dic_arr[m+1][(2**n) -1])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, m = [int(i) for i in input().split()]
costs = []
boxes = []

for i in range(m):
    c, bi = [int(i) for i in input().split()]
    costs.append(c)    
    box = [int(k)-1 for k in input().split()]
    boxes.append(box)

dp = [[-1 for i in range(3025)] for j in range(m+5)]


for mask in range((1<<n)-1, -1, -1):
    for idx in range(m, -1, -1):
        if mask == (1<<n)-1:
            dp[idx][mask] = 0
            continue
        if idx == m:
            dp[idx][mask] = 10**18
            continue
        dp[idx][mask] = dp[idx+1][mask]
        cur = 0
        for poss in boxes[idx]:
            cur |= (1<<poss)
        dp[idx][mask] = min(dp[idx][mask], dp[idx+1][mask|cur] + costs[idx])

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, m = [int(i) for i in input().split()]
costs = []
boxes = []

for i in range(m):
    c, bi = [int(i) for i in input().split()]
    costs.append(c)    
    box = [int(k)-1 for k in input().split()]
    boxes.append(box)

dp = [[-1 for i in range(20)] for j in range(n+5)]


for mask in range((1<<n)-1, -1, -1):
    for idx in range(m, -1, -1):
        if mask == (1<<n)-1:
            dp[idx][mask] = 0
            continue
        if idx == m:
            dp[idx][mask] = 10**18
            continue
        dp[idx][mask] = dp[idx+1][mask]
        cur = 0
        for poss in boxes[idx]:
            cur |= (1<<poss)
        dp[idx][mask] = min(dp[idx][mask], dp[idx+1][mask|cur] + costs[idx])

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, m = [int(i) for i in input().split()]
costs = []
boxes = []

for i in range(m):
    c, bi = [int(i) for i in input().split()]
    costs.append(c)    
    box = [int(k)-1 for k in input().split()]
    boxes.append(box)

dp = [[-1 for i in range(20)] for j in range(n+5)]

def f(idx, mask):
    '''
    at key idx, mask stores
    the current boxes i already have

    returns the min cost to get this
    '''
    if mask == (1<<n)-1:
        return 0
    if idx == m:
        return 10**18
    if dp[idx][mask] != -1:
        return dp[idx][mask]
    ans = f(idx+1, mask)
    isnew = 0
    curkeymask = 0
    for possiblebox in boxes[idx]:
        curkeymask |= (1<<possiblebox)

    ans = min(ans, costs[idx]+f(idx+1, mask|curkeymask))
    dp[idx][mask] = ans
    return ans

ans = f(0, 0)
if ans == 10**18:
    print(-1)
else:
    print(f(0, 0))

Submission status: Runtime Error

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('ap(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: Runtime Error

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


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1
            ), args[2::2])
    ))
    dp = DP(keys, n)

    return str(
        dp.search_min_cost(0, 0)
    )


class DP:
    def __init__(self, keys: list, n: int):
        self.keys = keys
        self.mask = int('1'*n, 2)

    @lru_cache(maxsize=None)
    def search_min_cost(self, index: int, unlocked: int) -> int:
        ret = 0

        if len(self.keys) == index:
            if unlocked != self.mask:
                ret = -1

        else:
            a, C = self.keys[index]
            take = self.search_min_cost(index+1, C | unlocked)
            skip = self.search_min_cost(index+1, unlocked)

            if take == -1 and skip == -1:
                ret = -1
            elif take == -1:
                ret = skip
            elif skip == -1:
                ret = a + take
            else:
                ret = min(a+take, skip)

        return ret


def set2bin(S: set, n: int, start: int = 0) -> int:
    ret = 0
    for s in S:
        ret += 2**(s-start)
    return ret


def bin2int(B: list) -> int:
    ret = 0
    for n in range(len(B)):
        if B[n]:
            ret += 2**n

    return ret


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

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1, initial=False
            ), args[2::2])
    ))
    dp = DP()

    return str(
        dp.search_min_cost(
            keys, np.array([False for _ in range(n)], dtype=bool)
        )
    )


class DP:
    def __init__(self):
        self.cache = {}

    def search_min_cost(self, keys: list, unlocked: list) -> int:
        ret = 0
        args = '{},{}'.format(len(keys), bin2int(unlocked))

        if args in self.cache.keys():
            ret = self.cache[args]

        elif len(keys) == 0:
            if not all(unlocked):
                ret = -1

        else:
            a, C = keys[0]
            take = self.search_min_cost(keys[1:], C | unlocked)
            skip = self.search_min_cost(keys[1:], unlocked)

            if take == -1 and skip == -1:
                ret = -1
            elif take == -1:
                ret = skip
            elif skip == -1:
                ret = a + take
            else:
                ret = min(a+take, skip)

        self.cache[args] = ret
        return ret


def set2bin(S: set, n: int, start: int = 0, initial: bool = True) -> list:
    ret = np.array([initial for _ in range(n)], dtype=bool)
    for s in S:
        ret[s-start] = not initial
    return ret


def bin2int(B: list) -> int:
    ret = 0
    for n in range(len(B)):
        if B[n]:
            ret += 2**n

    return ret


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

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1, initial=False
            ), args[2::2])
    ))

    return str(
        search_min_cost(keys, np.array([False for _ in range(n)], dtype=bool))
    )


cache = {}


def search_min_cost(keys: list, unlocked: list) -> int:
    ret = 0
    args = str((len(keys), unlocked))

    if args in cache.keys():
        ret = cache[args]

    elif len(keys) == 0:
        if not all(unlocked):
            ret = -1

    else:
        a, C = keys[0]
        take = search_min_cost(keys[1:], C | unlocked)
        skip = search_min_cost(keys[1:], unlocked)

        if take == -1 and skip == -1:
            ret = -1
        elif take == -1:
            ret = skip
        elif skip == -1:
            ret = a + take
        else:
            ret = min(a+take, skip)

    cache[args] = ret
    return ret


def set2bin(S: set, n: int, start: int = 0, initial: bool = True):
    ret = np.array([initial for _ in range(n)], dtype=bool)
    for s in S:
        ret[s-start] = not initial
    return ret


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

Submission status: Runtime Error

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(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: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 
#print(b)
def box(i,bo):#i :i番目の鍵 b空いている宝箱
    #if(0 not in bo):
        #i=M
        #return 0
    #elif(i==M and 0 in bo):
        #return 1e+20
    
    if(i==M):
        if(0 in bo):
            return 1e+20
        else:
            return 0
    else:
        if(0 not in bo):
            return 0
    
        else:
        
            p1 = box(i+1,bo)

            new_bo = bo.copy()
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1

            p2 = box(i+1,new_bo)+a[i]
            return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)
    
#宝箱はN(<=12)個

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 
print(b)
def box(i,bo):#i :i番目の鍵 b空いている宝箱
    #if(0 not in bo):
        #i=M
        #return 0
    #elif(i==M and 0 in bo):
        #return 1e+20
    
    if(i==M):
        if(0 in bo):
            return 1e+20
        else:
            return 0
    else:
        if(0 not in bo):
            i=M-1
            return 0
    
        else:
        
            p1 = box(i+1,bo)

            new_bo = bo.copy()
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1

            p2 = box(i+1,new_bo)+a[i]
            return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)
    
#宝箱はN(<=12)個

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 
print(b)
def box(i,bo):#i :i番目の鍵 b空いている宝箱
    #if(0 not in bo):
        #i=M
        #return 0
    #elif(i==M and 0 in bo):
        #return 1e+20
    
    if(i==M):
        if(0 in bo):
            return 1e+20
        else:
            return 0
    else:
        if(0 not in bo):
            i=M
            return 0
    
        else:
        
            p1 = box(i+1,bo)

            new_bo = bo.copy()
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1

            p2 = box(i+1,new_bo)+a[i]
            return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)
    
#宝箱はN(<=12)個

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 

def box(i,bo):#i :i番目の鍵 b空いている宝箱
    if(0 not in bo):
        return 0
    elif(i==M and 0 in bo):
        return 1e+20
    
    else:
        
        p1 = box(i+1,bo)
        
        new_bo = bo.copy()
        for k in range(len(b[i])):
            new_bo[b[i][k]] += 1
            
        p2 = box(i+1,new_bo)+a[i]
        return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 

def box(i,bo):#i :i番目の鍵 b空いている宝箱
    if(0 not in bo):
        return 0
    elif(i==M and 0 in bo):
        return 1e+20
    
    else:
        
        p1 = box(i+1,bo)
        
        new_bo = bo.copy()
        try:
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1
        except:
            print(i,b,"error")
        p2 = box(i+1,new_bo)+a[i]
        return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)
    
#宝箱はN(<=12)個

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 

def box(i,bo):#i :i番目の鍵 b空いている宝箱
    if(i==M and 0 not in bo):
        return 0
    elif(i==M and 0 in bo):
        return 1e+20
    else:
        
        p1 = box(i+1,bo)
        
        new_bo = bo.copy()
        try:
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1
        except:
            print(i,b,"error")
        p2 = box(i+1,new_bo)+a[i]
        return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 

print(b)
def box(i,bo):#i :i番目の鍵 b空いている宝箱
    if(i==M and 0 not in bo):
        return 0
    elif(i==M and 0 in bo):
        return 1e+20
    else:
        
        p1 = box(i+1,bo)
        
        new_bo = bo.copy()
        try:
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1
        except:
            print(i,b)
        p2 = box(i+1,new_bo)+a[i]
        return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 


def box(i,bo):#i :i番目の鍵 b空いている宝箱
    if(i==N and 0 not in bo):
        return 0
    elif(i==N and 0 in bo):
        return 1e+20
    else:
        
        p1 = box(i+1,bo)
        
        new_bo = bo.copy()
        for k in range(len(b[i])):
            new_bo[b[i][k]] += 1
        p2 = box(i+1,new_bo)+a[i]
        #print(min([p1,p2]))
        return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 


def box(i,bo):#i :i番目の鍵 b空いている宝箱
    if(i==N and 0 not in bo):
        return 0
    elif(i==N and 0 in bo):
        return 1e+15
    else:
        
        p1 = box(i+1,bo)
        
        new_bo = bo.copy()
        for k in range(len(b[i])):
            new_bo[b[i][k]] += 1
        p2 = box(i+1,new_bo)+a[i]
        #print(min([p1,p2]))
        return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+15):
    print(-1)
else:
    print(num)