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: Wrong Answer

Solution code:
INF = 10**9

N, M = map(int, input().split())
key = []
for _ in range(M):
    ab = list(map(int, input().split()))
    box = list(map(int, input().split()))
    index = sum(list(map(lambda x:2**(x-1), box)))
    ab.append(index)
    key.append(ab)
dp = [[key[0][0] if (i & ~key[0][2]) == 0 else INF for i in range(2**N)]]
for j in range(1, M):
    next = [0 for _ in range(2**N)]
    for i in range(2**N):
        next[i] = min(dp[j-1][i], dp[j-1][(i & ~key[j][2])]+key[j][0])
    dp.append(next)
if dp[-1][-1] > 10**7:
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
inf = 10**6
key_box = [[] for _ in range(m)]
key_price = [0] * m
box_price = [inf] * (n+1)
box_key = [set([]) for _ in range(n+1)]
price2box = {inf: {i for i in range(1, n+1)}}
for i in range(m):
    a, _ = map(int, input().split())
    key_price[i] = a
    for c in map(int, input().split()):
        key_box[i].append(c)
        if box_price[c] > a:
            price2box[box_price[c]].remove(c)
            if a in price2box.keys():
                price2box[a].add(c)
            else:
                price2box[a] = {c}
            box_price[c] = a
            box_key[c] = {i}
        elif box_price[c] == a:
            box_key[c].add(i)

for i in range(1, n+1):
    if not box_key[i]:
        print(-1)
        exit()

whole_boxes = {i for i in range(1, n+1)}
ans = 0
for price, boxes in sorted(price2box.items(), reverse=True):
    for i in range(1, n+1):
        if i not in whole_boxes and i in boxes:
            boxes.remove(i)
            
    while boxes:
        cnt = {}
        for box in boxes:
            for k in box_key[box]:
                if k in cnt.keys():
                    cnt[k] += 1
                else:
                    cnt[k] = 1
        mc = 0
        for i, v in cnt.items():
            mc = max(mc, v)
        for i, v in cnt.items():
            if cnt[i] == mc:
                isOpen = False
                for b in key_box[i]:
                    if b in whole_boxes:
                        # print("open box {} by key {}".format(b, i))
                        isOpen = True
                        whole_boxes.remove(b)
                        if b in boxes:
                            boxes.remove(b)
                        for w in box_key[b]:
                            if w in cnt:
                                cnt[w] -= 1
                if isOpen:
                    ans += price


print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
inf = 10**6
key_box = [[] for _ in range(m)]
key_price = [0] * m
box_price = [inf] * (n+1)
box_key = [set([]) for _ in range(n+1)]
price2box = {inf: {i for i in range(1, n+1)}}
for i in range(m):
    a, _ = map(int, input().split())
    key_price[i] = a
    for c in map(int, input().split()):
        key_box[i].append(c)
        if box_price[c] > a:
            price2box[box_price[c]].remove(c)
            if a in price2box.keys():
                price2box[a].add(c)
            else:
                price2box[a] = {c}
            box_price[c] = a
            box_key[c] = {i}
        elif box_price[c] == a:
            box_key[c].add(i)

for i in range(1, n+1):
    if not box_key[i]:
        print(-1)
        exit()
ans = 0
for price, boxes in price2box.items():
    while boxes:
        cnt = {}
        for box in boxes:
            for k in box_key[box]:
                if k in cnt.keys():
                    cnt[k] += 1
                else:
                    cnt[k] = 1

        mc = 0
        for i, v in cnt.items():
            mc = max(mc, v)
        for i, v in cnt.items():
            if cnt[i] == mc:
                isOpen = False
                for b in key_box[i]:
                    if b in boxes:
                        # print("open box {} by key {}".format(b, i))
                        isOpen = True
                        boxes.remove(b)
                        for w in box_key[b]:
                            cnt[w] -= 1
                if isOpen:
                    ans += price

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
inf = 10**6
key_box = [[] for _ in range(m)]
key_price = [0] * m
box_price = [inf] * (n+1)
box_key = [[] for _ in range(n+1)]
price2box = {inf: {i for i in range(1, n+1)}}
for i in range(m):
    a, _ = map(int, input().split())
    key_price[i] = a
    for c in map(int, input().split()):
        key_box[i].append(c)
        if box_price[c] > a:
            price2box[box_price[c]].remove(c)
            if a in price2box.keys():
                price2box[a].add(c)
            else:
                price2box[a] = {c}
            box_price[c] = a
            box_key[c].append(i)

for i in range(1, n+1):
    if not box_key[i]:
        print(-1)
        exit()
ans = 0
for price, boxes in price2box.items():
    # print(price, boxes)
    while boxes:
        cnt = {}
        for box in boxes:
            for k in box_key[box]:
                if k in cnt.keys():
                    cnt[k] += 1
                else:
                    cnt[k] = 1

        mc = 0
        for i, v in cnt.items():
            mc = max(mc, v)
        for i, v in cnt.items():
            if v == mc:
                isOpen = False
                for b in key_box[i]:
                    if b in boxes:
                        isOpen = True
                        boxes.remove(b)
                if isOpen:
                    ans += price

print(ans)

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
inf = 10**6
cc = [0] * m
cost = [inf] * (n+1)
key = [inf] * (n+1)

for i in range(m):
    a, _ = map(int, input().split())
    cc[i] = a
    for c in map(int, input().split()):
        if cost[c] > a:
            cost[c] = a
            key[c] = i

cnt = {}
ans = 0
for i in range(1, n+1):
    if cost[i] == inf:
        print(-1)
        exit()
    ans += cost[i]
    k = key[i]
    if k in cnt.keys():
        cnt[k] += 1
    else:
        cnt[k] = 1

for i, v in cnt.items():
    if v > 1:
        ans -= (v - 1) * cc[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
dp = [float("inf")]*(2**N)
dp[0] = 0
for i in range(1, M+1):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    d = 0
    for j  in range(1, N+1):
        if j in c:
            d += 2**(j-1)
    for j in range(2**N):
        dp[j | d] = min(dp[j | d], dp[j] + a)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
b = []
c = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(int, input().split()))
    ci_int = 0
    for hako in ci:
        hako -= 1
        ci_int += 2**hako
    a.append(ai)
    b.append(bi)
    c.append(ci_int)
#print(a)
#print(b)
#print(c)

dp = [[float("inf")]*(2**n) for _ in range(m+1)]
#dp[i][S]はi番目までのカギをいくつか使ってSになるようなコストの最小値
#Sは2進数で表現できる。例）１と３の箱が開けられる状態->0b101
dp[0][0] = 0
for i in range(m):
    for s in range(2**n):
        # i番目のカギを使用しない場合
        dp[i+1][s] = min(dp[i+1][s], dp[i][s])
        # 使用する場合
        dp[i+1][s | c[i]] = min(dp[i+1][s|c[i]], dp[i][s] + a[i])
print(dp[m][2**n-1])

Submission status: Wrong Answer

Solution code:
import copy
N, M = map(int, input().split())
key = [0] * M
bin_max = (2 ** N) 
dp = [[float('inf')] * (bin_max) ]
for i in range(M):
  a, _ =  map(int, input().split())
  c = list(map(int, input().split()))
  temp = 0
  for j in c:
    temp += (1 << (j-1))
  key[i] = ([a,temp])
  
for i in range(0,M):
  b = key[i][1]
  value = key[i][0]
  dp_low = copy.copy(dp[i])
  for j in range(1,bin_max):
    if j & b == j and dp[i][j] > value:
      dp_low[j] = value
    if dp[i][j] != float('inf'):
      next_b = j | b
      next= dp[i][j] + value
      if dp[i][next_b] > next:
        dp_low[next_b] = next
  dp.append(dp_low)
ans = -1 if dp[M-1][bin_max - 1] == float('inf') else dp[M-1][bin_max - 1]
print(ans)

Submission status: Wrong Answer

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

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(b):
        num = 2 ** (c[j] - 1)
        for k in range(2 ** n):
            if dp[k] != float("inf") and dp[k] - int(dp[k]) != 0:
                dp[k | num] = min(dp[k | num], dp[k])
            else:
                dp[k | num] = min(dp[k | num], dp[k] + a + 0.1)
    for j in range(2 ** n):
        if dp[j] != float("inf"):
            dp[j] = int(dp[j])
if dp[2 ** n - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** n - 1])

Submission status: Wrong Answer

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()



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

    ans =10**9+1
    for j in range(1<<N):
        S =set()
        con =0
        for i in range(M):
            if j & (1 << i):
                con +=A[i]
                S = S | C[i]
        if len(S)==N:
            ans =min(ans,con)

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




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dp =[float("INF")]*(2**N)
dp[0] = 0
for i in range(1,M+1):
    a,b = map(int,input().split())
    tmp = 0
    for c in list(map(int,input().split())):
        tmp += 1 << (c-1)
    for j in range(2**N):
        target = j|tmp
        dp[target] = min(dp[j]+a,dp[target])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
key=[]
for _ in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  bi=0
  for i in c:
    bi+=2**(i-1)
  key.append([a,bi])
dp=[10**10]*(2**n)
dp[0]=0
for k in key:
  for b in range(2**n):
    dp[b|k[1]]=min(dp[b|k[1]],dp[b]+k[0])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
keys=[None]*m
INF = 10**10
dp=[INF]*(2**n)
dp[0]=0
for i in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  cond=0
  for j in c:
    cond+=2**(j-1)
  keys[i]=[a,cond]
for key in keys:
  for sta in range(2**n):
        dp[sta|key[1]]=min(dp[sta|key[1]],dp[sta]+key[0])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
"""
宝箱の全組み合わせ2**N通りに対して、動的計画法で最小値を求める。
memo[boxes] => boxesに含まれる箱全てを開錠するのに必要なコスト。
memo[boxes]を求める場合は、まず、boxesをそのまま包括するような組み合わせからコストの候補を取ってくる。これは、O((2**N)*N)で探索可能。
次に、boxesをboxes[:i]とboxes[i:]で分割して再帰的に探索してコストの候補を取ってくる。これはO(N).
なお、すでに最小解が求まっている組み合わせに対しては、Flagを立てておくことで無駄な処理を省く。
全体でO((2**N)**2*N)かかるが、まあ間に合う。
"""
from itertools import combinations
N,M = map(int,input().split())
tmp = [i for i in range(1,N+1)]
memo = {}
for i in range(1,N+1):
    for cmb in list(combinations(tmp,i)):
        memo[cmb] = [float("INF"),False]

for _ in range(M):
    a,b = map(int,input().split())
    boxes = tuple(map(int,input().split()))
    memo[boxes][0] = min(memo[boxes][0],a)

def f(boxes):
    #boxesに含まれる箱全てを開錠するのに必要な最小コストを返す関数
    if not memo[boxes][1]:
        candidates = []
        for k,v in memo.items():
            for b in boxes:
                if b not in k:
                    break
            else:
                candidates.append(v[0])
        
        if len(boxes)>=2:
            for i in range(1,len(boxes)):
                candidates.append(f(boxes[:i])+f(boxes[i:]))
        
        memo[boxes][0] = min(candidates)
        memo[boxes][1] = True
    return memo[boxes][0]

ans = f(tuple(tmp))
if ans == float("INF"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
"""
宝箱の全組み合わせ2**N通りに対して、動的計画法で最小値を求める。
memo[boxes] => boxesに含まれる箱全てを開錠するのに必要なコスト。
memo[boxes]を求める場合は、まず、boxesをそのまま包括するような組み合わせからコストの候補を取ってくる。これは、O((2**N)*N)で探索可能。
次に、boxesをboxes[:i]とboxes[i:]で分割して再帰的に探索してコストの候補を取ってくる。これはO(N).
なお、すでに最小解が求まっている組み合わせに対しては、Flagを立てておくことで無駄な処理を省く。
全体でO((2**N)**2*N)かかるが、まあ間に合う。
"""
from itertools import combinations
N,M = map(int,input().split())
tmp = [i for i in range(1,N+1)]
memo = {}
for i in range(1,N+1):
    for cmb in list(combinations(tmp,i)):
        memo[cmb] = [float("INF"),False]

for _ in range(M):
    a,b = map(int,input().split())
    boxes = tuple(map(int,input().split()))
    memo[boxes][0] = min(memo[boxes][0],a)

def f(boxes):
    #boxesに含まれる箱全てを開錠するのに必要な最小コストを返す関数
    if not memo[boxes][1]:
        candidates = []
        for k,v in memo.items():
            for b in boxes:
                if b not in k:
                    break
            else:
                candidates.append(v[0])
        
        if len(boxes)>=2:
            for i in range(1,len(boxes)):
                candidates.append(f((boxes[:i]))+f(boxes[i:]))
        
        memo[boxes][0] = min(candidates)
        memo[boxes][1] = True
    return memo[boxes][0]

ans = f(tuple(tmp))
if ans == float("INF"):
    ans = -1
print(ans)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
abc = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    abc.append([a,b,c])

# 解説AC
dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, _, ci) in enumerate(abc, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(dp[-1][-1])

Submission status: Wrong Answer

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][S],dp[i-1][S&~(2**(a-1))]+A[i][0])
    print(dp[M][2**N-1])
else:
    print(-1)

Submission status: Wrong Answer

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][S],dp[i-1][S&~a]+A[i][0])
    print(dp[M][2**N-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def min2(x,y):
    return x if x < y else y

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

large = 1<<100
dp = [[large]*(1<<N + 1) for _ in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0
data = []
for i in range(M):
    a, b = map(int, input().split())
    bit = 0
    for c in map(int, input().split()):
        c -= 1
        bit = bit|1<<c
    data.append((a, bit))
data.sort()
for i, x in enumerate(data):
    a, bit = x
    for p in range(1<<N):
        dp[i+1][p|bit] = min(dp[i][p] + a, dp[i][p|bit], dp[i+1][p|bit])
print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] != large else -1)

Submission status: Wrong Answer

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

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

for i in range(M):
  a, b = map(int, input().split())
  c = sum(map(lambda x: 1 << (int(x)-1), input().split()))
  for j in range(1<<N):
    m = j|c
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][m] = min(dp[i+1][m], dp[i][m], dp[i][j] + a)

ans = dp[-1][-1]

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

Submission status: Wrong Answer

Solution code:
from itertools import product
N,M = map(int,input().split())
K = {i:[] for i in range(1,M+1)}
for i in range(1,M+1):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    K[i]=[a,c]
INFTY = 10**10
dp = [[INFTY for _ in range(2**N)] for _ in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0
for i in range(1,M+1):
    for j in range(2**N):
        dp[i][j] = dp[i-1][j]
        s = bin(j)[2:]
        s = "0"*(N-len(s))+s
        b = K[i][1]
        si=""
        for k in range(N):
            if k+1 not in b:
                si += "0"
            else:
                si += "1"
        s = list(s)
        for k in range(N):
            if si[k]=="1":
                s[k] = "0"
        s = "".join(s)
        dp[i][j] = min(dp[i][j],dp[i-1][int(s,2)]+K[i][0])
print(dp[M][2**N-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
c=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
  c.append(list(map(int,input().split())))
import numpy as np
t=tuple([2]*n)

from collections import defaultdict
dp={():0}
for i in range(m):
  a,b=ab[i]
  sc=set(c[i])
  dptmp={}
  for k,v in dp.items():
    s=set(k)
    s|=sc
    t=tuple(sorted(list(s)))
    #print(t,v+a)
    if t in dp:
      dptmp[t]=min(v+a,dp[t] if t not in dptmp else dptmp[t])
    else:
      dptmp[t]=v+a
  for k in dptmp:
    if k in dp:
      dp[k]=min(dp[k],dptmp[k])
    else:
      dp[k]=dptmp[k]
      
t=tuple(range(1,n+1))
if t in dp:
  print(dp[t])
else:
  print(-1)
#print(t)
#print(dp)

Submission status: Wrong Answer

Solution code:
# 解説配信
# https://atcoder.jp/contests/abc142/submissions/7774707
INF = 1001001001
n, m = map(int, input().split())
key = dict()
for i in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in map(int, input().split()):
        c -= 1
        s |= 1 << c
    key[s] = a
key = sorted(key.items(), key=lambda x: x[0])

dp = [INF] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for k, v in key:
        t = s | k
        cost = dp[s] + v
        dp[t] = min(dp[t], cost)

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

Submission status: Wrong Answer

Solution code:
# 解説配信
# https://atcoder.jp/contests/abc142/submissions/7774707
INF = 1001001001
n, m = map(int, input().split())
key = dict()
for i in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in map(int, input().split()):
        c -= 1
        s |= 1 << c
    key[s] = a

dp = [INF] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for k, v in key.items():
        t = s | k
        cost = dp[s] + v
        dp[t] = min(dp[t], cost)

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

Submission status: Wrong Answer

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

keys=[[] for _ in range(N)]
dp=[-1]*(2**N)
dp[0]=0

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

    op=2**N-1

    for cc in c:
        op-=2**(cc-1)

    for cc in c:
        keys[cc-1].append((op,a))


def rec(current):
    if dp[current]>-1:
        return dp[current]

    ret=10**10

    i=0
    tmp=current
    while tmp&1==0:
        i+=1
        tmp=tmp>>1
    
    for op,a in keys[i]:
        ret=min(ret,a+rec(current&op))
    
    if ret==10**10:
        dp[current]=-1
        return -1
    
    dp[current]=ret
    return ret

print(rec(2**N-1))

Submission status: Wrong Answer

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7


n,m=MI()
data=[]
for i in range(m):
    a,b=MI()
    c=LI()
    u=0
    for x in c:
        u+=2**(x-1)
    data.append([a,u])
data.sort()
#print(data)
dp=[[0]+[inf]*(2**n-1) for i in range(m+1)]
dp[0]=[inf]*(2**n)
dp[0][0]=0
#print(dp)
for i in range(m):
    for j in range(2**n):
        dp[i+1][j|data[i][1]]=min(dp[i+1][j|data[i][1]],dp[i][j|data[i][1]],dp[i][j]+data[i][0])
        #print(i+1,j|data[i][1],dp[i][j|data[i][1]],dp[i][j]+data[i][0])
    #print()

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

Submission status: Wrong Answer

Solution code:
INF = 10**18

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 = tuple(map(int,input().split()))
    C.append(c)
    
dp = [[INF for j in range(2**N)] for i in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    s = 0
    for k in range(B[i]):
        s += 2**(C[i][k] - 1)
    for j in range(2**N):
        dp[i + 1][j | s] = min(dp[i + 1][j | s], dp[i][j | s], dp[i][j] + A[i])
res = dp[M][2**N - 1]

print(res if res != INF else -1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
inf =  10**15
dp = [[inf]*2**N for _ in range(M+1)]
dp[0][0] = 0

def main():
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([2**(c-1) for c in C])
    for j in range(2**N):
      if dp[i][j] == inf:
        continue
      else:
        dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a)
  print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np

n, m = map(int, input().split())
price = np.zeros(m, dtype=int)
treasure = np.zeros(m, dtype=int)
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << (c - 1)
dp = np.ones(1 << n, dtype=int) * (10 ** 8 + 1)
dp[0] = 0
for bit in range(1 << n):
  next_bit = treasure | bit
  next_cost = price + dp[bit]
  dp[next_bit] = np.minimum(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

n, m = map(int, input().split())
price = np.zeros(m, dtype=int)
treasure = np.zeros(m, dtype=int)
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << (c - 1)
dp = np.ones(1 << n, dtype=int) * (10 ** 8 + 1)
dp[0] = 0
for bit in range(1 << n):
  dp[bit | treasure] = np.minimum(dp[bit | treasure], dp[bit] + price)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split()) 
asl = []
for _ in range(M):
    a, b = map(int, input().split()) 
    cl = list(map(int, input().split())) 
    s = 0
    for c in cl:
        s += 1<<(c-1)
    asl.append([a,s])

dp = [10**8]*(2**N)
dp[0] = 0
for i in range(2**N):
    for as_v in asl:
        a, s = as_v
        dp[i|s] = min(dp[i]+a ,dp[i|s])

ans = dp[2**N-1]
if ans == 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    dp = [10**10 for _ in [0]*(2**n)]
    dp[0] = 0
    for _ in range(m):
        a,b = map(int,ipt().split())
        c = [int(i) for i in ipt().split()]
        ext = []
        bs = 0
        non = []
        for i in range(n):
            if i+1 in c:
                bs += 2**i
                ext.append(2**i)
            else:
                non.append(2**i)
        for i in range(2**b):
            ps = 0
            for j in range(b):
                if (i>>j)&1:
                    ps += ext[j]
            if dp[ps] > a:
                dp[ps] = a
        for i in range(2**len(non)):
            ps = 0
            for j in range(len(non)):
                if (i>>j)&1:
                    ps += non[j]
            if dp[ps+bs] > dp[ps]+a:
                dp[ps+bs] = dp[ps]+a
    if dp[2**n-1] >= 10**10:
        print(-1)
    else:
        print(dp[2**n-1])
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    dp = [10**10 for _ in [0]*(2**n)]
    dp[0] = 0
    for _ in range(m):
        a,b = map(int,ipt().split())
        c = [int(i) for i in ipt().split()]
        ext = []
        bs = 0
        non = []
        for i in range(n):
            if i+1 in c:
                bs += 2**i
                ext.append(2**i)
            else:
                non.append(2**i)
        fmt = "0"+str(len(non))+"b"
        fmte = "0"+str(len(ext))+"b"
        for i in range(2**len(ext)):
            ib = list(map(int,format(i,fmte)))
            ps = 0
            for i in range(len(ext)):
                ps += ib[i]*ext[i]
            if dp[ps] > a:
                dp[ps] = a
        for i in range(2**len(non)):
            ib = list(map(int,format(i,fmt)))
            ps = 0
            for i in range(len(non)):
                ps += ib[i]*non[i]
            if dp[ps+bs] > dp[ps]+a:
                dp[ps+bs] = dp[ps]+a
    if dp[2**n-1] >= 10**10:
        print(-1)
    else:
        print(dp[2**n-1])
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

INF = 10**20
def main():
    N,M = map(int,input().split())

    key = []
    min_list = [[INF] * 2 for _ in range(N+1)]
    for i in range(M):
        a,_ = map(int,input().split())
        c = set(map(int,input().split()))
        key.append((a,c)) # 値段, 開ける宝箱のset
        for j in range(1,N+1):
            if j in c:
                if min_list[j][0] > a:
                    min_list[j][0] = a # j: 宝箱の名前, val: 最小の値段
                    min_list[j][1] = i

    ans = INF
    # print(min_list)
    for i in range(2**(N+1)):
        sum_cost = 0
        tkr = set()
        # print("///////")
        for j in range(1,N+1):
            if (i >> j) & 1:
                if min_list[j][0] == INF:
                    print(-1)
                    exit()

                # print(min_list[j])
                sum_cost += min_list[j][0]
                tkr = tkr.union(key[min_list[j][1]][1])
                # print(j,key[min_list[j][1]][1])

        # print(sum_cost,tkr)
        if len(tkr) == N:
            ans = min(ans,sum_cost)



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



if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Cost = []
for i in range(M):
    a, b = map(int, input().split())
    c = 0
    K = list(map(int, input().split()))
    for j in range(b):
        c += 2**(K[j]-1)
    Cost.append([c, a])

dp = [[float("inf")]*(2**N+1) for _ in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Cost = []
for i in range(M):
    a, b = map(int, input().split())
    c = 0
    K = list(map(int, input().split()))
    for j in range(b):
        c += 2**(K[j]-1)
    Cost.append([c, a])

dp = [[float("inf")]*(2**N+1) for _ in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
import itertools

N, M = map(int, input().split())
Cost = {}
for i in range(M):
    a, b = map(int, input().split())
    key = tuple(map(int, input().split()))
    c = Cost.get(key, 10**6)
    if a < c:
        Cost[key] = a

origin = list(range(1,N+1))
ans = float("inf")
All_list = list(itertools.permutations(origin))
for All in All_list:
    for i in range(2**N):
        start = 0
        c = 0
        judge = 0
        for j in range(N):
            if ( (i>>j)& 1 ) or j == N-1:
                if not tuple(All[start:j+1]) in Cost:
                    judge = 1
                    break
                else:
                    c += Cost[tuple(All[start:j+1])]
                    start = j + 1
        if judge == 0:
            ans = min(ans,c)

if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Cost = {}
for i in range(M):
    a, b = map(int, input().split())
    key = tuple(map(int, input().split()))
    c = Cost.get(key, 10**6)
    if a < c:
        Cost[key] = a

All = list(range(1,N+1))
ans = float("inf")
for i in range(2**N):
    start = 0
    c = 0
    judge = 0
    for j in range(N):
        if ( (i>>j)& 1 ) or j == N-1:
            if not tuple(All[start:j+1]) in Cost:
                judge = 1
                break
            else:
                c += Cost[tuple(All[start:j+1])]
                start = j + 1
    if judge == 0:
        ans = min(ans,c)

if ans == float("inf"):
    print(-1)
else:
    print(ans)