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:
#鍵i = a_i円,etc b=[1 4 5]を開けられる money=0
#"""
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(a,b)

#num = 0
#"""
#N,M=2,3
#a=[10,15,30]
#b=[[0],[1],[0,1]]
#"""

def box(i,bo):#i :i番目の鍵 b空いている宝箱
    #print(bo)
    if(i==N and 0 not in bo):
        #print(i,bo)
        return 0
    elif(i==N and 0 in bo):
        return 1e+12
    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)]
print(box(0,box_))

Submission status: Runtime Error

Solution code:
#鍵i = a_i円,etc b=[1 4 5]を開けられる money=0
#"""
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(a,b)

#num = 0
#"""
#N,M=2,3
#a=[10,15,30]
#b=[[0],[1],[0,1]]
#"""

def box(i,bo):#i :i番目の鍵 b空いている宝箱
    #print(bo)
    if(i==N and 0 not in bo):
        #print(i,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)]
box(0,box_)

Submission status: Runtime Error

Solution code:
def dp(key,t):
    if key==m:
        if t==total:
            return 0
        else:
            return inf
    if memo[key][t]!=-1:
        return memo[key][t]
    a=dp(key+1,t|tre[key])+cost[key]
    b=dp(key+1,t)
    ans=min(a,b)
    memo[key][t]=ans
    
    return ans
  
n,m=map(int,input().split())
total=2**n-1
cost=[0]*(m)
tre=[0]*(m)
inf=10**9
memo=[[-1 for i in range(total+1)] for j in range(m)]
for i in range(m):
    c,q=map(int,input().split())
    cost[i]=c
    t=[int(i) for i in input().split()]
    temp=0
    for x in t:
        temp|=1<<(x-1)
    tre[i]=temp
ans=dp(0,0)
if ans==inf:
    print(-1)
else:
    print(ans)

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())
    prices = list(map(lambda _: int(_.split()[0]), args[1::2]))
    targets = []
    for C in args[2::2]:
        b = np.array([0 for _ in range(n)])
        for i in map(int, C.split()):
            b[i-1] = 1
        # b = 0
        # for ci in map(int, C.split()):
        #     b += 2**ci
        targets.append(b)

    s = np.array([0 for _ in range(n)])
    for t in targets:
        s += t

    if not all(map(lambda x: x > 0, s)):
        return str(-1)

    total = sum(prices)

    keys = sorted(zip(prices, targets))
    for k in reversed(keys):
        p, t = k
        if all(map(lambda x: x > 0, s-t)):
            total -= p
            s = s-t

    # if len(set(itertools.chain.from_iterable(targets))) != n:
    #     return str(-1)

    return str(total)


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

inf = float("inf")
ans = [inf]*n**2
for _ in range(m):
    a,b = map(int,input().split())
    C = list(map(int,input().split()))
    res = 0
    for c in C:
        res |= 2**(c-1)
    ans[res] = a

aa = []
for i,a in enumerate(ans):
    if a == inf:continue
    aa.append([i,a])

for i,a in aa:
    for j,b in aa:
        ans[i|j] = min(ans[i|j],a+b)
print(ans[-1])

Submission status: Runtime Error

Solution code:
from math import inf
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])

Submission status: Runtime Error

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:

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

def main():
    N, M=map(int, input().split())
    a =[]
    c = []
    for i in range(2*M):
      if i%2 == 0:
        temp,_=map(int, input().split()) 
        a.append(temp)
      else:
        temp=list(map(int, input().split()))
        c.append(temp)
    a = np.array(a) 

    row = 2**M 
    boo = np.array([[int(j[i]) for i in range(M)] for j in  [bin(i)[2:].zfill(M) for i in range(row)]])
    table = np.zeros((row,N), dtype = 'int8')

    for i in range(row):
        ind_temp = np.array(list(set(itertools.chain.from_iterable(c*boo[i]))),dtype = int) -1
        table[i][ind_temp] = 1

    ind = np.where(np.all(table, axis=1))
    price = np.array([np.sum(a*boo[ind], axis = 1)])

    if price:
        print(np.min(price))
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools


N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 

row = 2**M 
con = [bin(i)[2:].zfill(M) for i in range(row)]
boo = np.array([[int(j[i]) for i in range(M)] for j in con])
table = np.zeros((row,N), dtype = 'int8')

for i in range(row):
    ind_temp = np.array(list(set(itertools.chain.from_iterable(c*boo[i]))),dtype = int) -1
    table[i][ind_temp] = 1

ind = np.where(np.all(table, axis=1))
price = np.array([np.sum(a*boo[ind], axis = 1)])
if price:
    print(np.min(price))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 
mini = -1
for n in range(M):
    for l in list(itertools.combinations(range(M),n+1)):
        temp = []
        for nn in l:
            temp = temp +c[l[nn]]
        temp = set(temp)
        temp = list(temp)
        if len(temp) == N:
            cost = sum(a[[np.array(l)]])
            if mini == -1 or mini > cost:
                mini = cost


print(mini)

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    inf = 10**9 #この10億は何に使う？->とにかくデカい数字。
    bit_bp = [inf for _ in range(2**(n))] #10億を2**n個並べる配列を作る。n=12 => 4096個
    bit_dp[0] = 0

    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))#鍵1個につきa,b,c1~cbを決める
        bit_n = 0
        for i in c:
            bit_n |= 1 << i - 1 #ここで何番目をあけられるのかをbit_nで定義する。1と3ならbit_n=(5)101、2と3なら110(6)
        for i in range(2**n):
            if bit_dp[i|bit_n] > bit_dp[i] + a: #
                bit_dp[i|bit_n] = bit_dp[i] + a

    if bit_dp[-1] >= inf:
        print(-1)
    else:
        print(bit_dp[-1])
                
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# if x < y:
#     z = x
# elif True:
#     z = y
# else:
#     z = 100
import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat

sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())

def main():
    n, m = map(int, raw_input().split())
    bf, af = [10000000 for i in range(1<<n)], [10000000 for i in range(1<<n)]
    bf[0] = 0
    for i in range(m):
        a, b = map(int, raw_input().split())
        ad = 0
        for st in map(int, raw_input().split()):
            ad |= 1<<(st-1)

        for st in range(1<<n):
            af[st|ad] = min(bf[st|ad], bf[st]+a, af[st|ad])
        # print af
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]



main()

Submission status: Runtime Error

Solution code:
#142e'' (高速化)
import copy
import random

N,M = map(int, input().split()) #N<=12,M<=10**3

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M): #10**3
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    #print(c,":",a)
    
    if c in openable_box_and_price:
        #print("重複")
        if openable_box_and_price[c] > a:
            #print("安値更新")
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
key_price = list(openable_box_and_price.values())
key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
box_and_openable_key = [[] for _ in range(N)]
key_number = 0

for openable_boxes in key_openable_box:  #10**3
    for openable_box in openable_boxes: #12
        box_and_openable_key[openable_box-1].append(key_number)

    key_number += 1

#print("########################")
#print(key_price)
#print(key_openable_box)    
#print(box_and_openable_key)
#print("########################")

#そもそも開けられる鍵が無い箱があったら-1を出力
for openable_key in box_and_openable_key:
    if not openable_key:
        print(-1)
        break
else:
    #すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
    cheapest_price = sum(key_price) #仮として最高値(全ての鍵を用いた場合)を入れる。
    keys_and_sum_price = {} #高速化のためにメモする
    key_combination = set()
    
    #key_combination_append = base_key_combination.append #appendを外に出して高速化
    #key_combination_pop = key_combination.pop #popを外に出して高速化
    
    def get_price_of_cheap_key_combination(box_number,cheapest_price,key_combination,now_price):
        #print("箱:",box_number)
        
        base_key_combination = copy.copy(key_combination)
                
        for openable_key in random.sample(box_and_openable_key[box_number],len(box_and_openable_key[box_number])):
            #print("added key:",openable_key)
            
            #既に鍵の組み合わせにあれば、処理省略させる
            if openable_key not in base_key_combination:
                #入ってなかったので処理
                
                if len(base_key_combination) != 0:
                    key_combination = base_key_combination | set([openable_key]) #!?
                    
                    if tuple(key_combination) not in keys_and_sum_price:
                        #print("計算して追加 ",end="")
                        now_price = keys_and_sum_price[tuple(base_key_combination)]
                        now_price += key_price[openable_key]
                        keys_and_sum_price[tuple(key_combination)] = now_price
                        #print(key_combination,":",now_price)
                    else:
                        #print("計算済み ",end="")
                        now_price = keys_and_sum_price[tuple(key_combination)]
                        #print(key_combination,":",now_price)
                else:
                    now_price = key_price[openable_key]
                    key_combination = set([openable_key])          
                    keys_and_sum_price[tuple(key_combination)] = now_price
                    #print("計算して追加(単独) ",end="")
                    #print(key_combination,":",now_price)
            #else:
                
                #print("skip ",end="")
                #print(key_combination,":",now_price)
                
            if now_price < cheapest_price: #値段を比較して枝刈する
                #安かったので、枝刈りしない。
                
                #全部の箱に対して鍵を選択済みか
                if box_number == N-1: #Yes→価格比較
                    #print("堀り終了")
                    #print("最安値更新:",now_price)
                    cheapest_price = now_price
                else: #No→再帰する
                    #print("深堀り")
                    cheapest_price = get_price_of_cheap_key_combination(box_number+1,cheapest_price,key_combination,now_price)
            #else:
                #print("枝刈り")
           
            #key_combination_pop(-1)
        
        return cheapest_price
    
    print(get_price_of_cheap_key_combination(0,cheapest_price,key_combination,0))

Submission status: Runtime Error

Solution code:
#76c
Sdash = list(str(input()))
T = list(str(input()))

#文字列 S′ を見つけ、これは文字列 S の 0 個以上 |S| 個以内の文字が ? に置き換わった文字列であることも分かりました。

#条件1：文字列 S の中に連続する部分文字列として英小文字から成る文字列 Tが含まれている。
#条件2：S は、条件1を満たす文字列の中で辞書順最小の文字列である。

#そのとき、鍵となる文字列 Sを出力しなさい。
#ただし、そのような文字列 S が存在しない場合は代わりに UNRESTORABLE と出力しなさい。

#後ろから探る
presence_flag = 0

for i in range(len(Sdash)-len(T),-1,-1):
    pickuped = Sdash[i:i+len(T)]
    for j in range(len(T)):
        if T[j] != pickuped[j] and pickuped[j] != "?":
            break
    else:
        if Sdash[i:i+len(T)]!=T: #文字列に?を含んでいる 
            presence_flag = 1
            Sdash[i:i+len(T)]=T
            break
        
if presence_flag == 1:
    for i in range(len(Sdash)):
        if Sdash[i]=="?":
            Sdash[i]="a"
    print(''.join(map(str, Sdash)))
else:
    print("UNRESTORABLE")
    
    
    
    

#76b
N = int(input()) #
K = int(input()) #

#電光掲示板に整数 1 が表示されているのを見ました。
#彼は、電光掲示板に対して、以下の操作 A, 操作 B をすることができます。
#操作 A： 電光掲示板に表示する整数を「今の電光掲示板の整数を 2倍にしたもの」に変える。
#操作 B： 電光掲示板に表示する整数を「今の電光掲示板の整数に Kを足したもの」に変える。
#操作 A, 操作 B 合計で N回 行わなければなりません。 
#そのとき、N 回の操作後の、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。
ans = 1

for i in range(N):
    if ans*2 <= ans+K:
        ans = ans*2
    else:
        ans += K
        
print(ans)





#76a
R = int(input()) #now rating
G = int(input()) #target rating

#現在のレーティングを aとする。
#次のコンテストで, パフォーマンス bを取ったとする。
#そのとき, レーティングは aと b の平均まで変化する。 
#after rating = (a+b)/2
#→G = (R+b)/2
# →2*G = R+b
#  →b = 2*G -R
print(2*G-R)





#142e'' (高速化)
import copy

N,M = map(int, input().split()) #N<=12,M<=10**3

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M): #10**3
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    #print(c,":",a)
    
    if c in openable_box_and_price:
        #print("重複")
        if openable_box_and_price[c] > a:
            #print("安値更新")
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
key_price = list(openable_box_and_price.values())
key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
box_and_openable_key = [[] for _ in range(N)]
key_number = 0

for openable_boxes in key_openable_box:  #10**3
    for openable_box in openable_boxes: #12
        box_and_openable_key[openable_box-1].append(key_number)

    key_number += 1

#print("########################")
#print(key_price)
#print(key_openable_box)    
#print(box_and_openable_key)
#print("########################")

#そもそも開けられる鍵が無い箱があったら-1を出力
for openable_key in box_and_openable_key:
    if not openable_key:
        print(-1)
        break
else:
    #すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
    cheapest_price = sum(key_price) #仮として最高値(全ての鍵を用いた場合)を入れる。
    keys_and_sum_price = {} #高速化のためにメモする
    key_combination = set()
    
    #key_combination_append = base_key_combination.append #appendを外に出して高速化
    #key_combination_pop = key_combination.pop #popを外に出して高速化
    
    def get_price_of_cheap_key_combination(box_number,cheapest_price,key_combination,now_price):
        #print("箱:",box_number)
        
        base_key_combination = copy.copy(key_combination)
                
        for openable_key in random.sample(box_and_openable_key[box_number],len(box_and_openable_key[box_number])):
            #print("added key:",openable_key)
            
            #既に鍵の組み合わせにあれば、処理省略させる
            if openable_key not in base_key_combination:
                #入ってなかったので処理
                
                if len(base_key_combination) != 0:
                    key_combination = base_key_combination | set([openable_key]) #!?
                    
                    if tuple(key_combination) not in keys_and_sum_price:
                        #print("計算して追加 ",end="")
                        now_price = keys_and_sum_price[tuple(base_key_combination)]
                        now_price += key_price[openable_key]
                        keys_and_sum_price[tuple(key_combination)] = now_price
                        #print(key_combination,":",now_price)
                    else:
                        #print("計算済み ",end="")
                        now_price = keys_and_sum_price[tuple(key_combination)]
                        #print(key_combination,":",now_price)
                else:
                    now_price = key_price[openable_key]
                    key_combination = set([openable_key])          
                    keys_and_sum_price[tuple(key_combination)] = now_price
                    #print("計算して追加(単独) ",end="")
                    #print(key_combination,":",now_price)
            #else:
                
                #print("skip ",end="")
                #print(key_combination,":",now_price)
                
            if now_price < cheapest_price: #値段を比較して枝刈する
                #安かったので、枝刈りしない。
                
                #全部の箱に対して鍵を選択済みか
                if box_number == N-1: #Yes→価格比較
                    #print("堀り終了")
                    #print("最安値更新:",now_price)
                    cheapest_price = now_price
                else: #No→再帰する
                    #print("深堀り")
                    cheapest_price = get_price_of_cheap_key_combination(box_number+1,cheapest_price,key_combination,now_price)
            #else:
                #print("枝刈り")
           
            #key_combination_pop(-1)
        
        return cheapest_price
    
    print(get_price_of_cheap_key_combination(0,cheapest_price,key_combination,0))

Submission status: Runtime Error

Solution code:
#dpがやや特殊なので、1次元的に走査したほうがよさそう。initializeもいらないし。
n,m = map(int, input().split())

inf = 10**9

dp =[inf for _ in range(2**n)]
dp[0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
  
    for j in range(2**n):
        jord = j | d
        dp[i][jord] = min(dp[i][jord], dp[i][j] + a)
            
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Runtime Error

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

dp = [[int("inf") for _ in range(2**n)] for _ in range(m)]
dp[0][0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
    for j in range(2**n):
        jord = j | d
        
        #initialize
        if i==0:
            dp[0][d] = a
        else:
            dp[i][jord] = min(dp[i-1][jord], dp[i-1][j] + a)
            
if dp[m-1][2**n-1] == int("inf"):
    print(-1)
else:
    print(dp[m-1][2**n-1])

Submission status: Runtime Error

Solution code:
import math
N, M = list(map(int, input().split(" ")))
abc = [[0, 0, 0] for i in range(M)]
for i in range(M):
  abc[i][0], abc[i][1] = list(map(int, input().split(" ")))
  c = list(map(int, input().split(" ")))
  for j in range(N):
    cbits = (1 << j) * (j+1 in c)
    abc[i][2] |= cbits

dp = [0 if i == 0 else math.inf for i in range(2**N)]
for i in range(M):
  for j in range(2**N):
    dp[j|abc[i][2]] = min(dp[j]+abc[i][0], dp[j|abc[i][2]])
print(dp[-1] if dp[-1] != math.inf else -1)

Submission status: Runtime Error

Solution code:
import math
N, M = list(map(int, input().split(" ")))
abc = [[0, 0, 0] for i in range(M)]
for i in range(M):
  abc[i][0], abc[i][1] = list(map(int, input().split(" ")))
  c = list(map(int, input().split(" ")))
  for j in range(N):
    cbits = (1 << j) * (j+1 in c)
    abc[i][2] |= cbits

dp = [0 if i == 0 else math.inf for i in range(2**N)]
for i in range(M):
  for j in range(2**N):
    dp[j|AB[i][2]] = min(dp[j]+AB[i][0], dp[j|AB[i][2]])
print(dp[-1] if dp[-1] != math.inf else -1)

Submission status: Runtime Error

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0
bits = set(0)
for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))
    add_set = set() # i個目の鍵を使ってbitsに新しく追加する分の状態を入れる
    for j in bits:
        jord = j | d
        dp[jord] = min(dp[jord], dp[j] + a)
        add_set.add(jord)
    bits |= add_set
    
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Submission status: Runtime Error

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    #d = sum((1<< (i - 1)) for i in  map(int, input().split()))  
    d = 0
    for c in c:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Submission status: Runtime Error

Solution code:
import copy

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


# a = [0, 0, 0]
# b = [0, 0, 0]
# c = [[0], [0], [0, 0]]
# N, M = [2, 3]
# a[0], b[0] = [10, 1]
# c[0][0] = 1
# a[1], b[1] = [15, 1]
# c[1][0] = 2
# a[2], b[2] = [30, 2]
# c[2][0:1] = [1, 2]

def dfs(money, idx, box):
    if idx == M:
        if len(box) == N:
            return money
        else :
            return -1
    b1 = copy.copy(box)
    b2 = copy.copy(box)
    b2 = b2.union(set(c[idx]))
    m1 = dfs(money, idx+1, b1)
    m2 = dfs(money + a[idx], idx+1, b2)
    #print(m1, m2)
    if not (-1 in [m1, m2]) :
        return min([m1, m2])
    else :
        return max([m1, m2])
print(dfs(0,0,set()))

Submission status: Runtime Error

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


# a = [0, 0, 0]
# b = [0, 0, 0]
# c = [[0], [0], [0, 0]]
# N, M = [2, 3]
# a[0], b[0] = [10, 1]
# c[0][0] = 1
# a[1], b[1] = [15, 1]
# c[1][0] = 2
# a[2], b[2] = [30, 2]
# c[2][0:1] = [1, 2]

def dfs(money, idx, box):
    if idx == M:
        if len(box) == N:
            return money
        else :
            return -1
    m1 = dfs(money, idx+1, box)
    m2 = dfs(money + a[idx], idx+1, box.union(set(c[idx])))
    #print(m1, m2)
    if not (-1 in [m1, m2]) :
        return min([m1, m2])
    else :
        return max([m1, m2])
print(dfs(0,0,set()))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())
n, m = rrd()

e = [[] for _i in range(1 << 13)]

p = []
for i in range(m):
    a, b = rrd()
    lst = list(rrd())
    g = 0
    for j in lst:
        g |= 1 << (j - 1)
    p.append((a, g))

for i in range(1 << n):
    for j in p:
        e[i].append((i | j[1], j[0]))
from math import inf

dis = [inf] * (1 << 13)
vis = [0] * (1 << 13)
dis[0] = 0

from heapq import *

q = [(0, 0)]
while len(q):
    ds, now = heappop(q)
    if vis[now]:
        continue
    vis[now] = 1
    for next, cost in e[now]:
        if dis[next] > dis[now] + cost:
            dis[next] = dis[now] + cost
            heappush(q, (dis[next], next))

if dis[(1 << n) - 1] == inf:
    print(-1)
else:
    print(dis[(1 << n) - 1])

Submission status: Runtime Error

Solution code:
#142e'' (高速化)
N,M = map(int, input().split()) #N<=12,M<=10**3

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M): #10**3
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    #print(c,":",a)
    
    if c in openable_box_and_price:
        #print("重複")
        if openable_box_and_price[c] > a:
            #print("安値更新")
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
key_price = list(openable_box_and_price.values())
key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
box_and_openable_key = [[] for _ in range(N)]
key_number = 0

#for openable_boxes in key_openable_box:  #10**3
openable_boxes = [openable_boxes for openable_boxes in key_openable_box]
for openable_box in openable_boxes: #12
    box_and_openable_key[openable_box-1].append(key_number)
    key_number += 1

#print("########################")
#print(key_price)
#print(key_openable_box)    
#print(box_and_openable_key)
#print("########################")

#そもそも開けられる鍵が無い箱があったら-1を出力
for openable_key in box_and_openable_key:
    if not openable_key:
        print(-1)
        break
else:
    #すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
    cheapest_price = sum(key_price) #仮として最高値(全ての鍵を用いた場合)を入れる。
    keys_and_sum_price = {} #高速化のためにメモする
    key_combination = []
    base_key_combination = []
    #key_combination_append = base_key_combination.append #appendを外に出して高速化
    #key_combination_pop = key_combination.pop #popを外に出して高速化
    
    def get_price_of_cheap_key_combination(box_number,cheapest_price,key_combination):
        #print("箱:",box_number)
        base_key_combination = key_combination
        
        for openable_key in box_and_openable_key[box_number]:
            
            #箱に対する鍵を追加する
            key_combination = base_key_combination + [openable_key]
            #print(key_combination,":",end="")
            
            #値段を見る…dictにあったら省略
            tuple_key_combination = tuple(set(key_combination))
            
            if tuple_key_combination not in keys_and_sum_price:
                #print("新規計算")
                if base_key_combination != []:
                    now_price = keys_and_sum_price[tuple(set(base_key_combination))] + key_price[openable_key] #sum(key_price[i] for i in tuple_key_combination) #重複していなければ新しいのはopenable_key
                else:
                    now_price = key_price[openable_key]
                    
                keys_and_sum_price[tuple_key_combination] = now_price
            else:
                #print("重複")
                now_price = keys_and_sum_price[tuple_key_combination]
                
            #print(now_price,",",cheapest_price)    
            #既に高かったら、そこで枝刈り
            
            if now_price < cheapest_price:
                #全部の箱に対して鍵を選択済みか
                if box_number == N-1: #Yes→価格比較
                    #print("堀り終了")
                    #print("最安値更新:",now_price)
                    cheapest_price = now_price
                else: #No→再帰する
                    #print("深堀り")
                    cheapest_price = get_price_of_cheap_key_combination(box_number+1,cheapest_price,key_combination)
            #else:
                #print("枝刈り")
           
            #key_combination_pop(-1)
        
        return cheapest_price
        
    print(get_price_of_cheap_key_combination(0,cheapest_price,key_combination))

Submission status: Runtime Error

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

def f(x):
    return int(x) - 1

A = []
#B = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    #B.append(b)
    C.append(list(map(f, input().split())))



def rec(cost, still_closed, d):
    """
    初期値
    cost = 0
    still_closed = [1]*N
    d = 0
    """
    if sum(still_closed) == 0:
        return cost
    if d == M:
        return - 1
    still_closed1 = copy.copy(still_closed)
    still_closed2 = copy.copy(still_closed)
    res1 = rec(cost, still_closed1, d + 1)
    for c in C[d]:
        still_closed[c] = 0
    res2 = rec(cost + A[d], still_closed, d + 1)
    if res1 == - 1 or res2 == - 1:
        return max(res1, res2)
    else:
        return min(res1, res2)

print(rec(0, [1]*N, 0))

Submission status: Runtime Error

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

def f(x):
    return int(x) - 1

A = []
#B = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    #B.append(b)
    C.append(list(map(f, input().split())))



def rec(cost, still_closed, d):
    """
    初期値
    cost = 0
    still_closed = [1]*N
    d = 0
    """
    if d == M:
        if sum(still_closed) == 0:
            return cost
        else:
            return - 1
    still_closed1 = copy.copy(still_closed)
    still_closed2 = copy.copy(still_closed)
    res1 = rec(cost, still_closed1, d + 1)
    for c in C[d]:
        still_closed[c] = 0
    res2 = rec(cost + A[d], still_closed, d + 1)
    if res1 == - 1 or res2 == - 1:
        return max(res1, res2)
    else:
        return min(res1, res2)

print(rec(0, [1]*N, 0))

Submission status: Runtime Error

Solution code:
def main():
    n ,m = map(int, input().split(' '))
    inf = 10**9
    bit_dp = [inf for _ in range(2**(n))]
    bit_dp[0] = 0
    for i in range(m):
        a, b = map(int, input().split(' '))
        c = list(map(int, input().split(' ')))
        bit_n = 0
        for i in c:
            bit_n |= 1 << i-1
        for i in range(2**(n)):
            if bit_dp[i|bit_n] > bit_dp[i] + a:
            bit_dp[i|bit_n] = bit_dp[i] + a
    if bit_dp[-1] >= inf:
        print(-1)
    else:
        print(bit_dp[-1])
if __name__ == '__main__':
    main()