Problem:


Score : 500 points

Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

All values in input are integers.

1 \leq N \leq 12

1 \leq M \leq 10^3

1 \leq a_i \leq 10^5

1 \leq b_i \leq N

1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}

Output

Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1.

Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

Sample Output 3

69942



Sample input:
2 3
10 1
1
15 1
2
30 2
1 2


Sample output:
25

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
a = []
pts = []
for i in range(m):
    la, lb = na()
    a.append(la)
    pt = 0
    for x in na():
        pt |= 1<<x-1
    pts.append(pt)

price = [99999999999999999] * (1<<n)
for i in range(m):
    price[pts[i]] = min(price[pts[i]], a[i])

dp = [9999999999999999] * (1<<n)
dp[0] = 0
for i in range(1<<n):
    if price[i] <= 100000:
        for j in range(1<<n):
            dp[j|i] = min(dp[j|i], dp[j] + price[i])
if dp[(1<<n)-1] >= 100000000:
    print(-1)
else:
    print(dp[(1<<n)-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]

ALL = 1<<n
dp = [10**9]*ALL
dp[0] = 0
for i in range(m):
    ndp = dp[:]
    a,b = [int(i) for i in readline().split()]
    c = [int(i)-1 for i in readline().split()]
    
    C = 0
    for i in c:
        C |= 1<<i
    
    for S in range(ALL):
        ndp[S|C] = min(ndp[S|C], dp[S] + a)
    
    dp = ndp

#    print(dp)


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print((n-(n>>1))/n)
    return

#B
def B():
    n,k = LI()
    h = LI()
    ans = 0
    for i in h:
        if i >= k:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    b = [(a[i],i+1) for i in range(n)]
    b.sort()
    ans = [b[i][1] for i in range(n)]
    print(*ans)
    return

#D
def D():
    def divisor(n):
        if n < 4:
            return set([n])
        res = set([1])
        i = 2
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.add(i)
            i += 1
        res.add(m)
        return res
    a,b = LI()
    if min(a,b) == 1:
        print(1)
        return
    s = divisor(a)
    t = divisor(b)
    s &= t
    print(len(s))
    return

#E
def E():
    n,m = LI()
    v = []
    for i in range(m):
        a,b = LI()
        c = LI()
        s = 0
        for j in c:
            s |= 1<<(j-1)
        v.append((a,s))
    l = 1<<n
    dp = [[float("inf")]*l for i in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        ni = i+1
        a,c = v[i]
        for b in range(l):
            if dp[i][b] == float("inf"):
                continue
            nb = b|c
            nd = dp[i][b]+a
            if nd < dp[ni][nb]:
                dp[ni][nb] = nd
            nd = dp[i][b]
            if nd < dp[ni][b]:
                dp[ni][b] = nd
    if dp[m][-1] == float("inf"):
        print(-1)
    else:
        print(dp[m][-1])
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    if box_price[i][0] == -1:
        print(-1)
        exit()
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b+1]:
                ks[kbx[b+1]] -= 1
                ks[key] += 1
                kbx1[b+1] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b+1]:
                ks[kbx[b+1]] -= 1
                ks[key] += 1
                kbx1[b+1] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b]:
                ks[kbx[b]] -= 1
                ks[key] += 1
                kbx1[b] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, M = read_ints()
    # key to cover
    cover = [0]*(1<<N)
    # key to cost
    costs = [0]*M
    INF = 10**9+1
    for i in range(M):
        a, b = read_ints()
        costs[i] = a
        for c in read_ints():
            cover[i] |= 1<<(c-1)
    # mask to cost
    mask_to_cost = [INF]*(1<<N)
    mask_to_cost[0] = 0
    for mask in range(1<<N):
        for i in range(M):
            mask_to_cost[cover[i]|mask] = min(mask_to_cost[cover[i]|mask], mask_to_cost[mask]+costs[i])
    return mask_to_cost[(1<<N)-1] if mask_to_cost[(1<<N)-1] != INF else -1


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
INFTY = 10**8+10
N,M = map(int,input().split())
A = {}
for i in range(1,M+1):
    a,b = map(int,input().split())
    C = list(map(int,input().split()))
    A[i] = (a,C)
C = {}
for i in range(1,M+1):
    for j in A[i][1]:
        if j not in C:
            C[j] = 0
        C[j] += 1
if len(C)==N:
    dp = [[INFTY for _ in range(2**N)] for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(1,M+1):
        for S in range(2**N):
            dp[i][S] = dp[i-1][S]
            for a in A[i][1]:
                dp[i][S] = min(dp[i-1][S&~a]+A[i][0])
    print(dp[M,2**N-1])
else:
    print(-1)

Submission status: Runtime Error

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

import numpy

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = numpy.zeros(2 ** 13).astype(numpy.int32)
  dp[1:] = MAX
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(dp.shape[0]):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if dp[2**(n+1)-2] != MAX:
    print(dp[2**(n+1)-2])
  else:
    print(-1)

if __name__=='__main__':
  main()

Submission status: Runtime Error

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

INF = 10**9
dp = [INF for i in range(N**2)]
dp[0] = 0
for i in range(N**2):
    for j in range(M):
        t = i | key[j][0]
        cost = key[j][1]
        dp[t] = min(dp[t], dp[i] + cost)
ans = dp[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

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

N, M = [int(s) for s in input().split()]
A = []
B = []
C = []

for i in range(M):
    a, b_s = [int(s) for s in input().split()]
    A.append(a)
    cnt = 0
    for b in b_s:
        cnt += 2 ** (b - 1)
    B.append(b)
    C.append([int(s) for s in input().split()])

dp = [[10 ** 9] * (2 ** N) for _ in range(M + 1)]

for i in range(1, M+1):
    for j in range(2 ** N):
        # 鍵iを使用した場合に dp[i-1][]から増える宝箱の数がkの時に
        # k: 開けることが可能となる宝箱の個数
        dp[i][j | b[i]] = min(dp[i-1][j] + A[i], dp[i-1][j | b[i]])

print(dp[M][2 ** N - 1])

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
A = [0] * M
C = [0] * M
for i in range(M):
    a, b = list(map(int, input().split()))
    A[i] = a
    c = list(map(int, input().split()))
    n = ['0'] * N
    for j in range(b):
        n[N-c[j]-2] = '1'
    C[i] = int(''.join(n), 2)

INF = float('inf')

dp = [[INF for i in range(2**N)] for j in range(M+1)]
dp[0][0] = 0

for i in range(1, M+1):
    for j in range(2**N):
        dp[i][j] = dp[i-1][j]

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1001)
n, m = list(map(int, input().split(' ')))

lll = []
for i in range(m):
  a, b = list(map(int, input().split(' ')))
  ccc = list(map(int, input().split(' ')))
  lll.append((a, b, set(ccc)))

memo = {}
def f(index, cost, opened):
  key = (index, str(sorted(opened)))
  if key in memo and memo[key] < cost:
    return 99999999999999999
  if index == m:
    return cost if len(opened) == n else 99999999999999999
  used = f(index + 1, cost + lll[index][0], opened.union(lll[index][2]))
  not_used = f(index + 1, cost, opened)
  memo[key] = min(memo.get(key, 99999999999999999), min(used, not_used))
  return memo[key]
ans = f(0, 0, set())
print(ans if ans < 99999999999999999 else -1)

Submission status: Runtime Error

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

lll = []
for i in range(m):
  a, b = list(map(int, input().split(' ')))
  ccc = list(map(int, input().split(' ')))
  lll.append((a, b, set(ccc)))

memo = {}
def f(index, cost, opened):
  key = (index, str(sorted(opened)))
  if key in memo and memo[key] < cost:
    return 99999999999999999
  if index == m:
    return cost if len(opened) == n else 99999999999999999
  used = f(index + 1, cost + lll[index][0], opened.union(lll[index][2]))
  not_used = f(index + 1, cost, opened)
  memo[key] = min(memo.get(key, 99999999999999999), min(used, not_used))
  return memo[key]
ans = f(0, 0, set())
print(ans if ans < 99999999999999999 else -1)

Submission status: Runtime Error

Solution code:
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
n, m = map(int, f.readline().split())
ab = []
c= []
keys = ["" for _ in range(m)]

for i in range(m):
    ab.append(list(map(int, f.readline().split())))
    kari = list(map(int, f.readline().split()))
    c.append(kari)
    for j in range(n):
        if j+1 in kari:
            keys[i] = keys[i]+"1"
        else:
            keys[i] = keys[i] + "0"

all_patterns = ["0","1"]
options = ["0", "1"]

for _ in range(n-1):
    all_patterns = [j+i for i in (options) for j in all_patterns]

dp_dict = dict()
for pattern in all_patterns:
    dp_dict[pattern] = 1e+10
dp_dict["0"*n] = 0

for j in range(m):
    for key in dp_dict.keys():
        kari1 = dp_dict[key]+ab[j][0]
        kari2 = dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")]
        if kari1 < kari2:
            dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")] = kari1

if dp_dict["1"*n] != 1e+10:
    print(dp_dict["1"*n])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    key = [0]
    box = [0]
    for _ in range(M):
        k,_ = LI()
        key.append(k)
        b = 0
        for c in LI():
            b += 2**(c-1)
        box.append(b)

    dp = [[INF] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(1,M+1):
        for j in range(2**N):
            dp[i][j] = min(dp[i-1][j],dp[i-1][j - (j&box[i])]+key[i])
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
dp = [float('inf')]*2 ** N
dp[0] = 0
for _ in range(N):
  a,b = map(int,input().split())
  c = sum([2**(int(i)-1) for i in input().split()])
  for s in range(2**N):
    t = s|c
    if dp[t] > dp[s] + a:
      dp[t] = dp[s] +a
ans = dp[-1]
if dp[-1] == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dp = [float('inf')]*(1<<n)
dp[0] = 0
for _ in range(m):
    a,b = map(int,input().split())
    sc = 0
    for e in map(int,input().split()):
        bit += 1<<(e-1)
    for i in range(1<<n):
        dp[i|bit] = min(dp[i|bit], dp[i]+a)
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Runtime Error

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append(s*(10**6)+a)


    node=2**N
    djk=Dijkstra(node)
    for i in xrange(0,M):
        for j in xrange(0,node):
            s=key[i]//(10**6)
            a=key[i]%(10**6)
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])


if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
解説AC



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

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

for i in range(m):
    for j in range(2**n):
        c = C[i]
        # 鍵を使用しない
        DP[i+1][j] = min(DP[i][j], DP[i+1][j])
        # 鍵を使用する
        nex = j | c
        DP[i+1][nex] = min(DP[i+1][nex], DP[i][j]+A[i])

ans = 10**9
for i in range(m):
    ans = min(DP[i][-1], ans)

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
A=[0]*m
B=[0]*m
C=[[] for _ in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
    c=list(map(int,input().split()))
    C[i]=c
#dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi=10**20
dp=[[infi for i in range(2**(n)+1)]for _ in range(m+1)]
dp[0][0]=0
for i in range(m):
    for s in range(2**(n-1)):
        ni=i+1
        ns=s
        #使わないとき
        dp[ni][ns]=min(dp[i][s], dp[ni][ns])
        #使うとき
        for c in C[i]:
            ns = s | 1<<(c-1)
        dp[ni][ns]=min(dp[ni][ns], dp[i][s]+A[i])
ans=dp[n][2**n-1]
print(ans if ans<infi else -1)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
A=[0]*m
B=[0]*m
C=[[] for _ in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
    c=list(map(int,input().split()))
    C[i]=c
#dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi=10**20
dp=[[infi for i in range(2**(n)+1)]for _ in range(n+1)]
dp[0][0]=0
for i in range(m):
    for s in range(2**(n-1)):
        ni=i+1
        ns=s
        #使わないとき
        dp[ni][ns]=min(dp[i][s], dp[ni][ns])
        #使うとき
        for c in C[i]:
            ns = s | 1<<(c-1)
        dp[ni][ns]=min(dp[ni][ns], dp[i][s]+A[i])
ans=dp[n][2**n-1]
print(ans if ans<infi else -1)

Submission status: Runtime Error

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
bit_cnt = 2 ** N # 箱は最大で12個
INF = 10 ** 10
dp = [INF] * bit_cnt
dp[0] = 0
for _ in range(M):
    price, b = lr()
    open = sum([2 ** (x-1) for x in lr()]) # 1と3の箱を開ける鍵なら101となる
    for j in range(bit_cnt):
        if dp[j|open] > dp[j] + price:
            dp[j|open] = dp[j] + price

if dp[-1] == INF:
    prnit(-1)
else:
    print(dp[-1])
# 解き直し08

Submission status: Runtime Error

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nが小さいのでdfs
N, M = lr()
keys = [None] * (M+1) # 1-indexed
for i in range(M):
    a, b = lr()
    c = set(lr())
    keys[i+1] = (a, c)

def dfs(m, fee, open):
    global answer
    if m == M+1:
        if len(open) == N:
            answer = min(answer, fee)
    else:
        dfs(m+1, fee+keys[m][0], open.union(keys[m][1]))
        dfs(m+1, fee, open)

INF = 10 ** 10
answer = INF
dfs(1, 0, set())
print(-1 if answer == INF else answer)
# 38

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 i in range(len(kagilst)**2):

        for k in takara[n]:
            lst=[0 for x in range(n)]
            for z in kagilst+[k]:
                for m in kagi[z][1]:
                    if m<len(lst):
                        lst[m]=1
            A=bin(i)[:2]
            A=list(reversed(list(A)))
            for i in range(len(A)-len(kagilst)):
                A.append("0")
            for a in range(len(kagilst)):

                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        if h<len(lst):
                            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:
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 i in range(len(kagilst)**2):

        for k in takara[n]:
            lst=[0 for x in range(n)]
            for z in kagilst+[k]:
                for m in kagi[z][1]:
                    if m<len(lst):
                        lst[m]=1
            A=bin(i)[:2]
            A=list(reversed(list(A)))
            for i in range(len(A)-len(kagilst)):
                A.append("0")
            for a in range(len(kagilst)):

                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        if h<len(lst):
                            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:
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 i in range(len(A)-len(kagilst)):
                A.append("0")
            for a in range(len(kagilst)):

                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        if h<len(lst):
                            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:
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 i in range(len(A))
            for a in range(len(kagilst)-len(kagilst)):
                A.append("0")
                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        if h<len(lst):
                            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:
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]:
                        if h<len(lst):
                            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)