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

inf = 10 ** 10

dp = [inf] * (1 << N)

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

    for j in range(1 << N):
        if dp[j] + a < dp[j | c]:
            dp[j | c] = dp[j] + a

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

Submission status: Runtime Error

Solution code:
n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m+1):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

csbit = []
for i in cs:
    csum = 0
    for j in i:
        csum += 2**(j-1)
    csbit.append(csum)

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    for j in range(1 << n):
        dp[j | csbit[i]] = min(dp[j | csbit[i]], dp[j] + ab[i][0])

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    # go = g
    # myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit += 1 << (d-1)

        for w in range(int(bin, 2) + 1):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

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

    return

# F


def F():
    N, M = map(int, input().split())

    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        unlock = 0
        for i in range(1, N+1):
            if i in c:
                unlock += 2 ** (i-1)
        key.append((a, unlock))

    dp = [[float('inf') for _ in range(2 ** N)] for _ in range(M + 1)]
    dp[0][0] = 0
    for i in range(M):
        for state in range(2 ** N):
            next_state = state | key[i][1]
            dp[i+1][next_state] = min(dp[i][state] + key[i]
                                      [0], dp[i+1][next_state])
        for state in range(2 ** N):
            dp[i+1][state] = min(dp[i+1][state], dp[i][state])

    if dp[-1][-1] < 10 ** 10:
        print(dp[-1][-1])
    else:
        print(-1)
    return


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

Submission status: Runtime Error

Solution code:
import itertools

N,M = map(int, input().split())
A = []
comp = sum(10**(x-1) for x in range(1,N+1))
for m in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  box = sum(10**(x-1) for x in c)
  A.append([box, a])

  for i in range(0,len(A)-1):
    A.append([A[0|i][0] + A[m][0], 
              A[0|i][1] + A[m][1]])

ans = min([A[x][1] for x in range(len(A))
           if A[x][0] >= comp] )

print(ans)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
dp = [float("inf") for i in range(n**2)]

for i in range(m):
    a, _ = [int(i) for i in input().split()]
    c = sum([2**(int(i)-1) for i in input().split()])
    for j in range(n**2):
        if j == 0:
            dp[c] = min(dp[c], a)

        elif dp[j] != float("inf"):
            dp[j|c] = min(dp[j|c], dp[j] + a)

print([dp[-1], -1][dp[-1] == float("inf")])

Submission status: Runtime Error

Solution code:
import numpy as np


n, m = [int(x) for x in input().split()]

costs = []
masks = []

for _ in range(m):
  costs.append(int(input().split()[0]))

  boxes = {int(x)-1 for x in input().split()}
  mask = ['1' if idx in boxes else '0' for idx in range(n)][::-1]
  mask = int(''.join(mask), 2)
  masks.append(mask)

  INF = int(10e8 + 1)
  #dp = np.full(1 << n, INF, dtype=int)
  dp = [INF] * (1 << n)
  dp[0] = 0

  for j in range(m):
    for i in range(1 << n):
      dp[i | masks[j]] = min(
        dp[i | masks[j]],
        dp[i] + costs[j]
      )

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

Submission status: Runtime Error

Solution code:
    import numpy as np
     
     
    n, m = [int(x) for x in input().split()]
     
    costs = []
    masks = []
     
    for _ in range(m):
        costs.append(int(input().split()[0]))
     
        boxes = {int(x)-1 for x in input().split()}
        mask = ['1' if idx in boxes else '0' for idx in range(n)][::-1]
        mask = int(''.join(mask), 2)
        masks.append(mask)
     
    INF = int(10e8 + 1)
    #dp = np.full(1 << n, INF, dtype=int)
    dp = [INF] * (1 << n)
    dp[0] = 0
     
    for j in range(m):
        for i in range(1 << n):
            dp[i | masks[j]] = min(
                    dp[i | masks[j]],
                    dp[i] + costs[j]
                )
     
    res = dp[-1] if dp[-1] != INF else -1
    print(res)

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include <bits/stdc++.h>
using namespace std;

constexpr const int maxs = 4096;
int dp[maxs];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	memset(dp, 0x3f, 16384);
	dp[0] = 0;
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b, s = 0;
		cin >> a >> b;
		while (b--) {
			int c;
			cin >> c;
			s ^= 1 << c - 1;
		}
		dp[s] = min(dp[s], a);
	}
	for (int i = 0; i != n; ++i) for (int all = (1 << n) - 1 ^ 1 << i, sub = all; sub; sub = sub - 1 & all)
		dp[sub] = min(dp[sub], dp[sub ^ 1 << i]);
	for (int s = 0; s != (1 << n); ++s) if (s != (s & -s))
		for (int t = s - 1 & s; t != s; t = t - 1 & s)
			dp[s] = min(dp[s], dp[t] + dp[s ^ t]);
	int mask = (1 << n) - 1;
	if (dp[mask] == 0x3f3f3f3f) dp[mask] = -1;
	cout << dp[mask] << endl;
}""")
call(('g++','e.cpp'))
call('./a.out')

Submission status: Runtime Error

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

def main():
    N, M = map(int,input().split())
    maxval = 10 ** (5 + 3 + 2)
    dp = [maxval] * (N ** 2)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        clist = list(map(int,input().split()))
        for ci in clist:
            c |= 1 << (ci - 1)
        newopen = set()
        for op in opened:
            check = op | c
            dp[check] = min(dp[op] + a, dp[check])
            newopen.add(c)
        opened = opened | newopen
        
    ans = dp[-1]
    if ans == maxval:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    N, M = map(int,input().split())
    maxval = 10 ** (5 + 3 + 2)
    dp = [maxval] * (N ** 2)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        clist = list(map(int,input().split()))
        for ci in clist:
            c |= 1 << (ci - 1)

        newopen = set()
        for op in opened:
            check = op | c
            chkval = dp[op] + a
            if dp[check] > chkval:
                dp[check] = chkval
                newopen.add(c)

        opened = opened | newopen
        
    ans = dp[-1]
    if ans == maxval:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    N, M = map(int,input().split())
    inf = 10 ** (5 + 3 + 2)
    dp = [inf] * (N ** 2)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        clist = list(map(int,input().split()))
        for ci in clist:
            c |= 1 << (ci - 1)

        newopen = set()
        for op in opened:
            check = op | c
            chkval = dp[op] + a
            if dp[check] > chkval:
                dp[check] = chkval
                newopen.add(c)

        opened = opened | newopen
        
    ans = dp[-1]
    if ans == inf:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    N, M = map(int,input().split())
    inf = 10 ** (5 + 3 + 2)
    dp = [inf] * (N ** 2)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        for ci in map(int,input().split()):
            c |= 1 << (ci - 1)

        newopen = set()
        for op in opened:
            check = op | c
            chkval = dp[op] + a
            if dp[check] > chkval:
                dp[check] = chkval
                newopen.add(c)

        opened = opened | newopen
        
    ans = dp[-1]
    if ans == inf:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().split())
dp = [-1] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline())
  s = sum(map(get_bits, map(int, sys.stdin.readline())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1])

Submission status: Runtime Error

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    cur = i % 2
    nxt = (i+1) % 2
    # 今回の鍵を買わない遷移
    dp[nxt] = dp[cur].copy()
    for j in range(1<<N):
        if dp[cur][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
ans = dp[M%2][-1]

if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
# import numpy as np

N, M = map(int, input().split())  # N個の宝箱, M個の鍵

keys = [None]*M
# 宝箱は1-N個
for i in range(M):
    a, b = map(int, input().split())  # 鍵のコスト, 開けれる宝箱の種類の数
    c_list = list(map(int, input().split()))  # 開けれる宝箱の種類
    s = 0  # 集合s
    for c in c_list:
        c -= 1  # idx 0 スタートにする
        s = s | 1<<c
    keys[i] = (s, a)  # (鍵を使って推移開けれる宝箱の集合, 鍵のコスト)

# dp = np.ones(1<<N) * np.inf  # N個の宝箱の状態を表す集合のパターンは 2^N 個ある
INF = 1e12
dp = [INF] * 1<<N
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[t] = min(dp[t], cost)

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

Submission status: Runtime Error

Solution code:
import sys
from functools import reduce

n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if len(reduce(lambda x, y: list(set(x)|set(y)), c))<n:
    print(-1)
    sys.exit()

mincost = sum(a)

def f(boxnum, cost, canopen):
    #cost = cost
    tmpcost = 100000
    for keynum in range(m):
        if boxnum in c[keynum]:
            if a[keynum]<=tmpcost:
                canopen = canopen|set(c[keynum])
                tmpcost = a[keynum]
            #elif a[keynum]=tmpcost:
            #   canopen = c[keynum]|set(c[keynum]) 
    return cost+tmpcost, canopen

cost=0
canopen = {}
for i in range(1, n+1): #box
    if i not in canopen:
        cost, canopen = f(i, cost, canopen)
    #print(i, canopen)
print(cost)

Submission status: Runtime Error

Solution code:
import sys
from functools import reduce

n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if len(reduce(lambda x, y: list(set(x)|set(y)), c))<n:
    print(-1)
    sys.exit()

mincost = sum(a)

def f(boxnum, cost):
    #cost = cost
    tmpcost = 100000
    for keynum in range(m):
        if boxnum in c[keynum] and a[keynum]<tmpcost:
            canopen = c[keynum]
            tmpcost = a[keynum]
    return cost+tmpcost, canopen

cost=0
canopen = {}
for i in range(1, n+1): #box
    if i not in canopen:
        cost, canopen = f(i, cost)
    #print(i, canopen)
print(cost)

Submission status: Runtime Error

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp_i=[set([j for j in range(M)]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( dp_i[i])
        min_key=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            if dp[new_i] > cost:
                dp[new_i] cost 
                min_key = j
                
        dp_i[i] = dp_i[i] - set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

Submission status: Runtime Error

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    temp = map(lambda x: 1<<(x-1), many_int())
    sums = sum(temp)
    treasures.append(sums)

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index-1):
    for j in range(M):
        new_i = int(bin(int(treasures[j],2) | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Runtime Error

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

max_index=2**N
INF=10**15

dp={}

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)
    dp[sums] = mon

for j in range(M):
    for i in dp.keys():
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

dp

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

Submission status: Runtime Error

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("0b"+"".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Runtime Error

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("0b"+"".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Runtime Error

Solution code:
def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


def main():
    INF = float('inf')

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

    dp = [[INF] * (1 << N) for _ in range(M + 1)]

    dp[0][0] = 0
    for i in range(M):
        a, m = keys[i]
        dpi = dp[i]
        dpi1 = dpi[i + 1]
        for j in range(1 << N):
            if dpi[j] == INF:
                continue
            if dpi[j] + a < dpi1[j | m]:
                dpi1[j | m] = dpi[j] + a
            if dpi[j] < dpi1[j]:
                dpi1[j] = dpi[j]

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


main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dp = [10**9]*(2**n)
for i in range(m):
  a,_ = map(int,input().split())
  c = list(map(int,input().split()))
  t = 0
  for x in c:
    t |= 1<<(x-1)
  for b in range(2**n):
    dp[b|t] = min(dp[b],dp[b+a])
if dp[-1] > 10**8:
  print(-1)
else:
  print(dp[-1])

Submission status: Runtime Error

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

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

inf = float('inf') 
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j] 
        if cost[i|move2] < cost[i]+a[j]:
        cost[i|move2] = cost[i]+a[j]

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])

Submission status: Runtime Error

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

for i in range(m):
    ai, bi = map(int, input().split())
    a.append(ai); b.append(bi)
    ci = [int(j) for j in input().split()]
    c.append(ci)

inf = 10**5

def calc_price(box_key_list):
    rtn = 0
    for bkl in box_key_list:
        if bkl == -1:
            rtn += inf
        else:
            rtn += a[bkl]
    return rtn

box_key_list = [-1] * n
total_price = calc_price(box_key_list)
flag = False

def solve(box_idx, price, box_key_list):
    global flag
    if box_idx >= n:
        if -1 not in box_key_list:
            flag = True
        return price

    for ki in range(m):
        if ki in box_key_list:
            continue
        if ki+1 not in c[ki]:
            continue

        box_key_list[box_idx] = ki
        
        price = min(price, calc_price(box_key_list), solve(box_idx+1, price, box_key_list))
        return price

price = solve(0, total_price, box_key_list)

if flag:
    print(price)
else:
    print("-1")

Submission status: Runtime Error

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

for i in range(m):
    ai, bi = map(int, input().split())
    a.append(ai); b.append(bi)
    ci = [int(j) for j in input().split()]
    c.append(ci)

inf = 10**5

def calc_price(box_key_list):
    rtn = 0
    for bkl in box_key_list:
        if bkl == -1:
            rtn += inf
        else:
            rtn += a[bkl]
    return rtn

box_key_list = [-1] * n
total_price = calc_price(box_key_list)
flag = False

def solve(box_idx, price, box_key_list):
    global flag
    if box_idx >= n:
        if -1 not in box_key_list:
            flag = True
        return price

    for ki in range(m):
        if ki in box_key_list:
            continue
        if ki+1 not in c[ki]:
            continue

        box_key_list[box_idx] = ki
        
        price = min(calc_price(box_key_list), solve(box_idx+1, price, box_key_list))
        return price

price = solve(0, total_price, box_key_list)

if flag:
    print(price)
else:
    print("-1")

Submission status: Runtime Error

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

def to_bit(s):
    r = 0
    for i in s:
        r |= 1 << (i - 1)
    return r

def main():
    N, M = map(int, input().split())
    a, c = [], []
    cd = {}
    ALL = (1 << N) - 1
    tall = 0
    FAIL = (10 ** 3) * (10 ** 5) + 1
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = to_bit(map(int, input().split()))
        c.append(cc)
        tall |= cc
        cd[cc] = min(cd.get(cc, FAIL), t)

    if tall != ALL:
        print(-1)
        return

    @lru_cache(maxsize=None)
    def helper(i, opened):
        if opened == ALL:
            return 0
        if i == M:
            return FAIL
        while opened | c[i] == opened:
            i += 1
            if i == M:
                return FAIL
        return min(a[i] + helper(i + 1, opened | c[i]),
                   helper(i + 1, opened))

    print(helper(0, 0))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        def k(s):
            if dp[s|c] > dp[s] + a
                dp[s|c] = dp[s] + a
        [k(s) for s in range(p)]
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i-1)) for i in input().split()])
        for s in range(p):
                t = s|c
                new = dp[s] + a
                if dp[t] > new:
                    dp[t] = new
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i-1)) for i in input().split()])
        for s in range(p):
                t = s|c
                new = dp[s] + a
                if dp[t] > new:
                    dp[t] = new
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
I=lambda:list(map(int,input().split()));n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a=I()[0];s=sum(2<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

Submission status: Runtime Error

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

set_check = set([i+1 for i in range(N)])

def findkey(step, set_in, sum):
  if set_check.issubset(set_in):
      return sum
  if step == M-1:
      return -1
  right = findkey(step+1, set_in, sum)
  left = findkey(step+1, set_in | set(c[step+1]), sum+a[step+1])
  if left == -1:
    return right
  if right == -1:
    return left
  return min(left, right)
print(findkey(-1, set([]), 0))

Submission status: Runtime Error

Solution code:
#Thank you for snuke!

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

dp = [10**9 for i in range(1 << N)]
dp[0] = 0
for s in range(1 << N) :
    for i in range(N) :
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)

ans = dp[-1] if dp[-1] != 10**9 else -1

print(ans)

Submission status: Runtime Error

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

set_check = set([i+1 for i in range(N)])

def findkey(step, set_in, sum):
  if step == M-1:
    if set_check.issubset(set_in):
      return sum
    else:
      return -1
  right = findkey(step+1, set_in, sum)
  left = findkey(step+1, set_in | set(c[step+1]), sum+a[step+1])
  if left == -1:
    return right
  if right == -1:
    return left
  return min(left, right)
print(findkey(-1, set([]), 0))

Submission status: Runtime Error

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
e=[(I()[0],[2**(n-i)for i in I()])for _ in'_'m]
I=9**9
dp=[I]*2**n
dp[0]=0
for i,d in enumerate(dp):
    if d==I:continue
    for a,c in e:
        b,x=i,d+a
        for j in c:b|=j
        if dp[b]>x:dp[b]=x
print(-(dp[-1]==I)or dp[-1])

Submission status: Runtime Error

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

set_check = set([i+1 for i in range(N)])

def findkey(step, set_in, sum):
  if step == M-1:
    if set_check.issubset(set_in):
      return sum
    else:
      return -1
  left = findkey(step+1, set_in | set(c[step+1]), sum+a[step+1])
  right = findkey(step+1, set_in, sum)
  if left == -1:
    return right
  if right == -1:
    return left
  return min(left, right)
print(findkey(0, set(c[0]), a[0]))

Submission status: Runtime Error

Solution code:
#途中
import copy

def main():
    n,m=map(int,input().split())#n：宝の数,m：鍵の数
    key=[None]*n
    price=[]
    for i in range(m):
        a,b=map(int,input().split())#この鍵はa円、b種類の宝を開けれる
        price.append(a)
        for j in list(map(int,input().split())):
            if key[j-1]==None:
                key[j-1]=[i]
            else:
                key[j-1].append(i)
    if None in key:
        print(-1)
        return
    ans=0
    for i in range(n):
        if len(key[i])==1:#この鍵は買うしかない
            ans+=price[key[i][0]]
            keySub=[]
            for j in key:
                if key[i][0] not in j:
                    keySub.append(j)
            key=copy.deepcopy(keySub)
    
    if key=[]:
        print(ans)
        return
    
    
    
main()

Submission status: Runtime Error

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

dp = [float("inf")] * (2 ** N)

dp[0] = 0

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

    key = 0

    for j in c:
        key += 2 ** (j-1)

    for j in range(2**N):
        if dp[j | num] > dp[j] + a:
            dp[j | num] = dp[j] + a

if dp[2 ** N - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** N - 1])