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:
n,m = map(int,input().split())
listA=[] #appendのために宣言が必要
i=0
a=[]
b=[]
c=[]
while True:
    try:
        if(i%2==0):
          i=i+1
          a1,b1=(list(map(int,input().split())))
          a.append(a1)
          b.append(b1)
          #listA.append(list(map(int,input().split())))
        else:
          i=i+1
          c.append(list(map(int,input().split())))	
    except:
        break;
        #または、quit(),os.exit()をして止める。

#print(listA)
#print(a)
#print(b)
#print(*c)
#偶数はa,b
get_=[]
money=[]
kei=0
for i in range(m):
  get_.extend(c[i])
  kei=kei+a[i]
  if(len(list(set(get_)))==n):
    money.append(kei)
  
print(min(money))

Submission status: Runtime Error

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

aa = []
bb = []
cc = []
for i in range(m):
  a,b =  map(int,input().split())
  aa.append(a)
  bb.append(b)
  cc.append(list(map(int,input().split())))

ot = set(list(range(1,13)))

while kagi>=12:

  lon = set(max(cc))
  dif = set(ot ^ lon)


  for i in range(m):

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)


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


C=[[] for i in range(N)]

for i in range(M):
	a,b=map(int,input().split())
	c=[int(x)-1 for x in input().split()]
	c.append(a)
	for j in range(len(c)-1):
		C[c[j]].append(c)

for i in range(N):
	C[i].sort(key=lambda x:len(x),reverse=True)
for i in range(N):
	if len(C[i])>1:
		t=C[i][0]
		for c in range(1,len(C[i])):
			f=True
			for k in range(len(C[i][c])-1):
				if t[k]!=C[i][c][k]:f=False
			if f and t[-1]<C[i][c][-1]:C[i].remove(C[i][c])


H=[[0]*2 for i in range(N)]
for i in range(N):
	H[i][0]=len(C[i])
	H[i][1]=i
H.sort()

ans=[10**9]

def dfs(d,u):
	f=True
	for i in d:
		if d[i]:f=False
	if f:
		ans[0]=min(ans[0],u)
		return
	
	for i in range(N):
		t=H[i][1]
		if d[t]:
			d[t]=False
			for c in C[t]:
				u+=c[-1]
				for k in range(len(c)-1):
					d[c[k]]=False
				dfs(d,u)
				for k in range(len(c)-1):
					d[c[k]]=True
				u-=c[-1]
			return

dfs([True]*N,0)

print(-1 if ans[0]==10**9 else ans[0])

Submission status: Runtime Error

Solution code:
import numpy as np
def dfs(cost,S,L,N,T):#L,N,Tは定数
    mn=10**10
    if len(S)==N:
        return cost
    for i in T:
        if i in S:
            continue
        else:
            bad=[]
            safe_cost=10**10
            for j,e in enumerate(L):
                if i in e[1] and len(S|e[1])-len(S)==1:
                        bad.append(j)
                        if e[0]<safe_cost:
                            safe_cost=e[0]
                            safe_idx=len(bad)-1
            if bad:
                bad[safe_idx]=None
            
            
            for j,e in enumerate(L):
                if j in bad:
                    continue
                if i in e[1]:
                    mn=min(mn,dfs(cost+e[0],(S|e[1]),L,N,T))

    return mn
                    


def main():
    full=set(list(range(1,13)))
    k=set()
    T=np.zeros(12)
    N,M=map(int,input().split())
    A=[]
    L=[]
    for i in range(M):
        a,_=map(int,input().split())
        C=set(map(int,input().split()))
        for c in C:
            T[c]+=1
            
        k=k.union(C)
        L.append((a,C))

    L.sort(key=lambda x:x[0])

    if len(k)<N:#全部の宝を開けるだけのカギがない
        return -1

    T=np.argsort(np.array(T))+1
    return dfs(0,set(),L,N,T)
    

print(main())

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
N, M = LI()
data = []
c_list =[]
combi_dict = {}
for m in range(M):
    a,b = LI()
    c = LI()
    data.append([a, b, c])
    c_key = ','.join([str(i) for i in c])
    if combi_dict.get(c_key) is None:
        combi_dict[c_key] = a
    else:
        combi_dict[c_key] = min(combi_dict[c_key], a)
#  perr(data)
#  perr(combi_dict)

# すべて開けることができない場合を除外
done_list = []
for d in data:
    for c in set(d[2]):
        if c not in done_list:
            done_list.append(c)
#  print(done_list)
if len(done_list) != N:
    print(-1)
    exit()

# 全部の箱を開けるということで、まず1の箱、2の箱というようにやる？
"""
まずどの鍵を使えばいいか
DPは？
単純にやると、どの鍵を使うかの組み合わせ全部求める
それだと最大MC12通りになる
鍵は1000個しかないことに注目
そもそも12個しか箱がないので、例えば、同じ組み合わせの箱をあけるとすると、無駄な鍵が絶対ある
例えば
1000円で1,2,3を開ける鍵と、100円で1,2,3を開ける鍵がある場合
減らせる
後は、箱番号ごとにリストにして、ひとつになるまで減らす
高いやつは怪しい
まず仮ぎめして、これ以上安くできるか検証
[[],
[['1,3,4', 67786, 22595.333333333332]],
[['2', 3497, 3497.0], ['2,3,4', 2156, 718.6666666666666]],
[['1,3,4', 67786, 22595.333333333332], ['2,3,4', 2156, 718.6666666666666], ['3', 86918, 86918.0]],
[['1,3,4', 67786, 22595.333333333332], ['2,3,4', 2156, 718.6666666666666]]
]
これなら
1 3 4
2
にして、1 3 4でまず検討
まず平均最低から決定

---
 ----
--
  -----
   ----
"""

kv_list = [[] for _ in range(0, N+1)]
for key, value in combi_dict.items():
    key_list =list(map(int, key.split(',')))
    length = len(key_list)
    average = value/len(key_list)
    for k in key_list:
        kv_list[k].append([key, value, average, length])
#  print(kv_list)
ans = []
#  kv_list.sort(key=lambda x: x[2])

for idx, kv in enumerate(kv_list):
    if len(kv) == 0: continue
    min_v = min([i[1] for i in kv])
    for item_idx, item in enumerate(kv):
        if item[3] == 1 and item[1] != min_v:
            del kv_list[idx][item_idx]
            break
#  print(kv_list)
data = [j for i in kv_list for j in i]
#  print(data)
# ここから組み合わせを求める
ans = inf
def dfs(idx, price, opened_list):
    if idx == M:
        if len(opened_list) == N:
            #  print(idx, price, opened_list)
            global ans
            ans = min(ans, price)
        return

    # 単純に使う場合、使わない場合
    next_v = data[idx]
    if not all(x in opened_list for x in next_v):
        keys = list(map(int, next_v[0].split(',')))
        new_opened = list(set(opened_list + keys))
        dfs(idx + 1, price+next_v[1], new_opened)
        dfs(idx + 1, price, opened_list)
dfs(0, 0, [])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab_list = []
c_list = []
nu = set()


class Item:
    def __init__(self, price, key):
        self.key = key
        self.price = price

for _ in range(m):
    ab_list.append(list(map(int, input().split())))
    c_list.append(set(list(map(int, input().split()))))

locks = set([i for i in range(1, n+1)])


def knap(i, locked):
    def solver(a, b):
        unlocked = a&b
        return a - unlocked
    if i>=m and not(locked == nu):
        return -(10**9)
    if i>=m:
        return 0
    if locked == nu:
        return 0
    new_locked = solver(locked, c_list[i])
    p1 = knap(i + 1, locked)
    if new_locked == locked:
        p2 = p1
    else:
        p2 = knap(i+1, solver(locked, c_list[i])) + ab_list[i][0]
    if p1 < 0 and p2 < 0:
        return -(10**9)
    elif p1 < 0:
        return p2
    elif p2 < 0:
        return p1
    elif p1 < p2:
        return p1
    else:
        return p2


kane = knap(0, locks)
if kane > 0:
    print(kane)
else:
    print(-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

box = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    box.append([a, c])

box.sort(key=lambda x: x[0])

memo = [0] * n
tmp = []

ans = 0

for i in range(m):
    cost = box[i][0]
    target = box[i][1]

    for t in target:
        t -= 1
        memo[t] += 1
    ans += cost
    tmp.append(i)

    cost_max = 0
    bit_max = 0
    for bit in range(2**(i+1)):
        memo_sub = [0] * n
        cost_sub = 0
        for j in range(i+1):
            if (1 << j) & bit:
                co = box[j][0]
                ta = box[j][1]
                cost_sub += co
                for t in ta:
                    t -= 1
                    memo_sub[t] += 1
        flag = 1
        for k in range(n):
            if memo_sub[k] >= memo[k]:
                flag = 0
        if flag:
            if cost_sub > cost_max:
                cost_max = cost_sub
                bit_max = bit

    for j in range(i+1):
        if (1 << j) & bit_max:
            tmp.remove(j)
            for t in box[j][1]:
                t -= 1
                memo[t] -= 1
    ans -= cost_max

for mi in memo:
    if mi == 0:
        print(-1)
        exit()

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
C = [0] * M
ML = [0] * M
Master = [False] * N
MAX = 0
dic = {}
f = False
for m in range(M):
  C[m], b = [int(x) for x in input().split()]
  ML[m] = tuple([int(x) for x in input().split()])
  if not f:
    for ml in ML[m]:
      if not Master[ml-1]:
        MAX += C[m]
        Master[ml-1] = True
        if not False in Master:
          f = True

if False in Master:
  print(-1)
  exit()

def dp(m, c, opened):
  global MAX
  if (m, c, tuple(opened)) in dic:
    return dic[(m, c, tuple(opened))]
  if not False in opened:
    return c
  if m == M:
    return MAX
  f = False
  opened2 = opened[:]
  if c + C[m] <= MAX:
    for ml in ML[m]:
      if opened2[ml-1] == False:
        opened2[ml-1] = True
        f = True
  if f:
    ret = min(dp(m + 1, c, opened[:]),dp(m + 1, c + C[m], opened2[:]))
    dic[(m, c, tuple(opened))] = ret
    MAX = min(MAX, ret)
    return ret
  else:
    ret = dp(m + 1, c, opened[:])
    dic[(m, c, tuple(opened))] = ret
    MAX = min(MAX, ret)
    return ret

print(dp(0, 0, [False] * N))

Submission status: Runtime Error

Solution code:
def solve(idx, total_cost, box_set: set):
  if idx >= M:
    if len(box_set) == N:
      return total_cost
    else:
      return -1

  unused = solve(idx+1, total_cost, box_set.copy())
  for e in keys[idx][1::]:
    box_set.add(e)
  used = solve(idx+1, total_cost+keys[idx][0], box_set.copy())

  if used == -1 and unused == -1:
    return -1
  elif used == -1:
    return unused
  elif unused == -1:
    return used
  else:
    return min(used, unused)

N, M = map(int, input().split())
keys = [[] for i in range(M)]

for i in range(M):
  cost, b = map(int, input().split())
  keys[i] = [cost] + list(map(int, input().split()))

print(solve(0, 0, set()))

Submission status: Runtime Error

Solution code:
import sys
import heapq
sys.setrecursionlimit(10000000)

def knap(i, used, cost, N, M, Key, K_cost):
    if i == N - 1:
        take = used | Key[i]
        take_cost = cost + K_cost[i]
        a = set([int(i) for i in range(N)])
        if  used == a: return cost
        elif take == a: return take_cost
        else: return -1
    else:
        take = used | Key[i]
        take_cost = knap(i+1, take, cost + K_cost[i], N, M, Key, K_cost)
        not_take_cost = knap(i+1, used, cost, N, M, Key, K_cost)
        if take_cost == not_take_cost == -1: return -1
        elif take_cost == -1: return not_take_cost
        elif not_take_cost == -1: return take_cost
        else: return min(take_cost, not_take_cost)
        

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Key = dict()
    K_cost = dict()
    for i in range(M):
        a, b = map(int, input().split())
        K_cost[i] = a
        Key[i] = set([int(c) - 1 for c in input().split()])

    print(knap(0, set(), 0, N, M, Key, K_cost))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
import heapq

def knap(i, used, cost, N, M, Key, K_cost):
    if i == N - 1:
        take = used | Key[i]
        take_cost = cost + K_cost[i]
        a = set([int(i) for i in range(N)])
        if  used == a: return cost
        elif take == a: return take_cost
        else: return -1
    else:
        take = used | Key[i]
        take_cost = knap(i+1, take, cost + K_cost[i], N, M, Key, K_cost)
        not_take_cost = knap(i+1, used, cost, N, M, Key, K_cost)
        if take_cost == not_take_cost == -1: return -1
        elif take_cost == -1: return not_take_cost
        elif not_take_cost == -1: return take_cost
        else: return min(take_cost, not_take_cost)
        

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Key = dict()
    K_cost = dict()
    for i in range(M):
        a, b = map(int, input().split())
        K_cost[i] = a
        Key[i] = set([int(c) - 1 for c in input().split()])

    print(knap(0, set(), 0, N, M, Key, K_cost))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [None] * M
for i in range(M):
    A, B, = map(int, input().split())
    C = [int(v) for v in input().split()]
    
    L[i] = (A, C)

ans = 10 ** 18
for i in range(1 << N):
    t = set()

    for j in range(N):
        if (i >> j) & 1:
            t.add(j)

    m = set([v for v in range(1, N + 1)])
    score = 0
    for p in t:
        a = L[p]
        score += a[0]
        m = m - set(a[1])

    if len(m) == 0:
        ans = min(ans, score)

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

Submission status: Runtime Error

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

def main():
    sys.setrecursionlimit(2000)
    N, M = map(int, input().split())
    a, c = [], []
    tall = set(range(1, N + 1))
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = frozenset(map(int, input().split()))
        c.append(cc)
        tall = tall - cc
    if tall:
        print(-1)
        return
    FAIL = sum(a) + 1

    @lru_cache(maxsize=None)
    def helper(i, left):
        if not left:
            return 0
        if i == M:
            return FAIL
        return min(a[i] + helper(i + 1, left - c[i]),
                   helper(i + 1, left))

    print(helper(0, frozenset(range(1, N + 1))))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

  
  n,m = map(int, input().split())
  bps = [0]*n
  keys = [0]*n
  for i in m:
    price = int(input())
    for j in map(int,input().split()):
      if price < bps[j]:
        bps[j] = price
        keys[j] = i+1
  
  if 0 in keys:
    print(-1)
  else:
    print(len(set(keys)))

if __name__ == '__main__':
  solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)


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


C=[[] for i in range(N)]

for i in range(M):
	a,b=map(int,input().split())
	c=[int(x)-1 for x in input().split()]
	c.append(a)
	for j in range(len(c)-1):
		C[c[j]].append(c)

H=[[0]*2 for i in range(N)]
for i in range(N):
	H[i][0]=len(C[i])
	H[i][1]=i
H.sort()

ans=[10**9]

def dfs(d,u):
	f=True
	for i in d:
		if d[i]:f=False
	if f:
		ans[0]=min(ans[0],u)
		return
	
	for i in range(N):
		t=H[i][1]
		if d[t]:
			d[t]=False
			for c in C[t]:
				u+=c[-1]
				for k in range(len(c)-1):
					d[c[k]]=False
				dfs(d,u)
				for k in range(len(c)-1):
					d[c[k]]=True
				u-=c[-1]
			return

dfs([True]*N,0)

print(-1 if ans[0]==10**9 else ans[0])

Submission status: Runtime Error

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

def main():
    sys.setrecursionlimit(2000)
    N, M = map(int, input().split())
    a, c = [], []
    tall = set(range(1, N + 1))
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = frozenset(map(int, input().split()))
        c.append(cc)
        tall = tall - cc
    if tall:
        print(-1)
        return
    FAIL = sum(a) + 1

    @lru_cache(maxsize=None)
    def helper(i, price, left):
        if not left:
            return price
        if i == M:
            return FAIL
        return min(helper(i + 1, price + a[i], left - c[i]),
                   helper(i + 1, price, left))

    print(helper(0, 0, frozenset(range(1, N + 1))))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab_list = []
c_list = []
nu = set()

class Item:
    def __init__(self, price, key):
        self.key = key
        self.price = price


items=[]

for _ in range(m):
    # ab_list.append(list(map(int, input().split())))
    # c_list.append(list(map(int, input().split())))
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    items.append(Item(a, c))

locks = set([i for i in range(1, n+1)])

def knap(i, locked):
    def solver(a, b):
        unlocked = a&b
        return a - unlocked
    if i>=len(items) and not(locked == nu):
        return -(10**9)
    if i>=len(items):
        return 0
    if locked == nu:
        return 0
    p1 = knap(i+1, locked)
    p2 = knap(i+1, solver(locked, items[i].key)) + items[i].price
    if p1 < 0 and p2 < 0:
        return -(10**9)
    elif p1 < 0:
        return p2
    elif p2 < 0:
        return p1
    elif p1 < p2:
        return p1
    else:
        return p2


price = knap(0, locks)
if price > 0:
    print(price)
else:
    print(-1)

Submission status: Runtime Error

Solution code:

def like_napsac(ite, price, box_set):
    if ite == M:
        if len(box_set) != N:
            return 10 ** 9
        else:
            return price
    else:
        return min(like_napsac(ite + 1, price, box_set), like_napsac(ite+1, price+key[ite][0], box_set | key_box[ite]))


N, M = map(int, input().split())
key = [0] * M
key_box = [0]*M
for i in range(M):
    key[i] = [0] * 2
    key[i][0], key[i][1] = map(int, input().split())
    key_box[i] = set([int(x) for x in input().split()])
ans = like_napsac(0, 0, set())
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
keys = {}
for i in range(M):
  keys[i] = []
  for j in range(2):
    if j == 0:
      n, m = [int(i) for i in input().split()]
      keys[i].append(n)
    else:
      op = set([int(i) for i in input().split()])
      keys[i].append(op)

memo = {}
def rec(i, not_opened):
  if len(not_opened) == 0:
    return 0
  elif i == M:
    return float("inf")
  if i in memo and tuple(not_opened) in memo[i]:
    return memo[i][tuple(not_opened)]
  val1 = keys[i][0] + rec(i+1, not_opened ^ (not_opened & keys[i][1]))
  val2 = rec(i+1, not_opened)
  val = min(val1, val2)
  if i not in memo:
    memo[i] = {}
  memo[i][tuple(not_opened)] = val
  return val

no = set([i+1 for i in range(N)])
val = rec(0, no)
if val == float("inf"):
  print(-1)
else:
  print(val)

Submission status: Runtime Error

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


C=[[] for i in range(N)]

for i in range(M):
	a,b=map(int,input().split())
	c=[int(x)-1 for x in input().split()]
	c.append(a)
	for j in range(len(c)-1):
		C[c[j]].append(c)

H=[[0]*2 for i in range(N)]
for i in range(N):
	H[i][0]=len(C[i])
	H[i][1]=i
H.sort()

ans=[10**9]

def dfs(d,u):
	f=True
	for i in d:
		if d[i]:f=False
	if f:
		ans[0]=min(ans[0],u)
	
	for i in range(N):
		t=H[i][1]
		if d[t]:
			d[t]=False
			for c in C[t]:
				u+=c[-1]
				for k in range(len(c)-1):
					d[c[k]]=False
				dfs(d,u)
				for k in range(len(c)-1):
					d[c[k]]=True
				u-=c[-1]
			return

dfs([True]*N,0)

print(-1 if ans[0]==10**9 else ans[0])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def readInts():
  return [int(s) for s in input().split(" ")]

def is_ok(opened):
  for b in opened:
    if not b:
      return False
  return True

def dfs(N, M, Ks, m, opened, s):
  if m >= M:
    return -1

  a, b, c = Ks[m]
  found = False
  opened_next = opened[:]

  for i in c:
    if not opened[i-1]:
      found = True
      opened_next[i-1] = True

  # not use
  cost = dfs(N, M, Ks, m+1, opened, s)

  # use
  cost_use = s + a
  if not is_ok(opened_next):
    cost_use = dfs(N, M, Ks, m+1, opened_next, s + a)

  if cost >= 0 and cost_use >=0:
    return min(cost, cost_use)
  elif cost < 0:
    return cost_use
  else:
    return cost

def main():
  N, M = readInts()
  Ks = []
  for m in range(M):
    a, b = readInts()
    c = readInts()
    Ks.append((a, b, c))

  opened = [False for _ in range(N)]
  print(dfs(N, M, Ks, 0, opened, 0))

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    abc = []
    for i in range(M):
        a, b = map(int, input().split())
        c = np.array(list(map(int, input().split()))) - 1
        abc.append((a, b, c))
    abc = sorted(abc)
    INF = int(1e10)
    dp = np.full(N, INF, dtype=int)

    ans = 0
    for i in range(M):
        a, b, c = abc[i]
        now = sum(dp[c])
        if a < now:
            dp[c] = np.minimum(dp[c], a)
            ans += a

    ok = True
    for i in range(N):
        if dp[i] == INF:
            ok = False
            break
    
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

# DPテーブルを初期化
dp = [10**9] * ((2**N) + 30)  # dp[010100011010]: 状態010100011010に到達するための最小コスト
dp[0] = 0

# ループを回す
for i in range(M):
    a, b = map(int, input().split())
    c = [int(i) for i in input().split()]

    bit = 0
    for cb in c:
        bit += 2**(cb-1)

    for fromb in range(2**N+1):
        dp[fromb | bit] = min(dp[fromb | bit], dp[fromb]+a)

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

Submission status: Runtime Error

Solution code:
use std::cmp::{min, Ordering};
use std::collections::VecDeque;
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main_c() {
    let n = read::<usize>();
    let aa = (0..n).map(|_| read::<usize>()).collect::<Vec<_>>();
    let mut x = aa
        .iter()
        .enumerate()
        .map(|(a, &b)| (b, a))
        .collect::<Vec<_>>();
    x.sort();

    let mut space = false;
    for (b, a) in x {
        if space {
            print!(" ");
        }

        print!("{}", a + 1);
        space = true;
    }
}

#[allow(dead_code)]
fn main() {
    let n = read::<usize>();
    let m = read::<usize>();
    let acc = (0..m)
        .map(|_| {
            let a = read::<usize>();
            let b = read::<usize>();
            let cc = (0..b).map(|_| read::<usize>()).collect::<Vec<_>>();
            let mut bit = 0;

            for &c in cc.iter() {
                bit |= 1 << (c - 1)
            }
            (a, bit)
        })
        .collect::<Vec<_>>();

    let len = 1 << n;
    let u_max = usize::max_value();
    let mut dp = vec![vec![u_max; len]; m + 1];
    dp[0][0] = 0;

    for i in 0..m {
        let (a, cc) = acc[i];
        for j in 0..len {
            if dp[i][j] == u_max {
                continue;
            }
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
            let temp = min(dp[i][j | cc], dp[i][j] + a);
            dp[i + 1][j | cc] = min(temp, dp[i + 1][j | cc]);
        }
    }

    let ans = dp[m][len - 1];
    if ans == u_max {
        println!("-1")
    } else {
        println!("{}", ans)
    }
}

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0] * M
keys = [0] * M
inf = 10 ** 12
for i in range(M):
    a[i], _ = map(int, input().split())
    c_list = list(map(int, input().split()))
    keys[i] = sum([2 ** j for j in range(N) if j + 1 in c_list])

dp = [inf] * (N ** 2)
dp[0] = 0

# print(keys)

for i in range(M):  # use key i
    for j in range(N ** 2):
        dp[j | keys[i]] = min(dp[j] + a[i], dp[j | keys[i]])
        # print(dp, j, keys[i], dp[j | keys[i]], dp[j], a[i])

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

Submission status: Runtime Error

Solution code:
n,m=[int(s) for s in input().split()]
key_ls=[]
for i in range(m):
  a,b=[int(s) for s in input().split()]
  op=[int(s) for s in input().split()]
  key_ls.append([a,op])
key_ls.sort()
#print(key_ls)
door=[0 for _ in range(n)]
door2=[1 for _ in range(n)]
cost=0
#####一番安い鍵から順にかっていく
while True:
  if door==door2 : break
  key=key_ls.pop(0)
  flag=0
  #まだ開いていない箱を開けられるか？
  for x in key[1]:
    if door[x-1]==0:
      flag=1
      break
  #開けられるなら購入
  if flag==1:
    cost+=key[0]
  for x in key[1]:
    door[x-1]=1
    
print(cost)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
c=[0]*(2000)
dp=[10**19]*(n+1)
dp[0]=0 
for i in range(m): 
    c[i],k=map(int,input().split())
    z=[int(i) for i in input().split()]
    if all(dp[x]!=10**19 for x in z):
        sm=dp[i]
        now=c[i]
        if now<sm: 
            for x in z:
                dp[x]=now 
    else: 
        for x in z:
            dp[x]=c[i]
f=1 
sm=set()
for i in range(1,n+1):
    if dp[i]==10**19:
        f=0 
    sm.add(dp[i])
#print(dp)
if f:
    print(sum(sm))
    
else:
    print(-1)

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    a, c = [], []
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = set(map(int, input().split()))
        c.append(cc)

    al = set(range(1, N + 1))
    print(helper(0, N, M, a, c, 0, al))

def helper(i, N, M, a, c, price, al):
    if not al:
        return price
    if i == M:
        return -1
    t = helper(i + 1, N, M, a, c, price + a[i], al - c[i])
    s = helper(i + 1, N, M, a, c, price, al)
    if t != -1 and s != -1:
        return min(t, s)
    else:
        return max(t, s)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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())
    c.append([j for j in map(int,input().split())])

s=set([])
for i in range(m):
    s=s|set(c[i])
if s!={i+1 for i in range(n)}:
    print(-1)

t1=[i for i in range(m) if 1 in c[i]]
dp=[0]*(n+1)
dp[1] = min(a[i] for i in t1)
for i in range(2,n+1):
    v=[]
    for j in range(1,i+1):
        r={k for k in range(j,i+1)}
        t=[i for i in range(m) if r.issubset(set(c[i]))]
        if len(t)>0:
            vtemp = dp[j-1]+min(a[i] for i in t)
            v.append(vtemp)
    dp[i]=min(v)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import heapq

N, M = [int(v) for v in input().split(' ')]

class Key:
    def __init__(self, cost, C):
        self.cost = cost
        self.C = C

key_array = []
for m in range(0, M):
    a, b = [int(v) for v in input().split(' ')]
    C = [int(v) - 1 for v in input().split(' ')]

    key_array.append(Key(a, C))


cost_heap = []

def search(box, choice, index, cost):
    if len(choice) == index:
        return

    key = key_array[index]

    choice[index] = 0
    next_index = index + 1
    search(box[:], choice, next_index, cost)

    for o in key.C:
        box[o] = True

    if all_open(box):
        enabled_cost = cost + key.cost
        heapq.heappush(cost_heap, enabled_cost)
        return

    choice[index] = 1
    search(box, choice, next_index, cost + key.cost)

def all_open(box):
    for b in box:
        if b == False:
            return False
    return True

box = [False] * N
choice = [0] * M 

search(box, choice, 0, 0)

if len(cost_heap) == 0:
    print(-1)
    exit()

print(heapq.heappop(cost_heap))

Submission status: Runtime Error

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

A=[]
B=[]
C=[]
for i in range(N):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  A.append(a)
  B.append(b)
  C.append(c)
  
print(A, B, C)