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:
N, M = map(int, input().split())

# 宝箱の数: N, 最大12
# 鍵の数: M, 最大1000
# 1番目の鍵の値段: a1
# 1番目の鍵が開けられる宝箱: c1[1] - c[b1]
# 鍵は自分の値段と開けられる宝箱リストの情報を持つ


class Key:
    """price: int, boxes: Set[int]"""

    def __init__(self, price, boxes):
        self.price = price
        self.boxes = boxes


keys = []
for _ in range(M):
    a, b = map(int, input().split())
    boxes = set(map(int, input().split()))
    keys.append(Key(a, boxes))

# 開けられる宝箱の数の降順、値段の昇順ソートで１位の鍵を選ぶ
# 残りの宝箱を開けられる数の降順、値段の昇順ソートで１位の鍵を選ぶ
# 全ての箱を開けられる鍵が揃うまで続ける

target_keys = []
remaining_unopened_box = set(range(1, N + 1))

ans = 0
while True:
    current_max_can_open = -1
    current_min_price = 10 ** 5
    current_target = 0
    for i, k in enumerate(keys):
        # 最大開封箱数がMaxでないならスキップ
        currnet_can_open = len(k.boxes)
        if currnet_can_open < current_max_can_open:
            continue
        # 価格が最低でないならスキップ
        if k.price > current_min_price:
            continue
        # ここまで来たら購入候補にする
        # 各種最大値、最小値を更新
        # print("I'll buy this " + str(i) + " key.")
        current_max_can_open = currnet_can_open
        current_min_price = k.price
        current_target = i
    # １ループ終えて最大開封箱数が-1なら-1を出力して終了
    if current_max_can_open == -1:
        ans = -1
        break
    # １ループ終えたら購入する
    target_keys.append(keys[current_target])
    # print(keys[current_target].price)
    target_boxes = keys[current_target].boxes
    # 残りの開封したい宝箱の数を減らす
    remaining_unopened_box -= target_boxes
    # print(remaining_unopened_box)
    # 残り0になればループを抜ける
    if len(remaining_unopened_box) == 0:
        # print("all boxes are opened!")
        # 回答を出力する
        ans = sum([k.price for k in target_keys])
        break
    # 鍵一覧から購入した鍵を削除する
    del keys[current_target]
    # print("last " + str(len(keys)) + "keys!")
    # 各鍵のboxesから、購入した鍵で開封できる宝箱を減らす
    for k in keys:
        k.boxes -= target_boxes

# ループ抜けたら回答出力
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A=[0]*M
B=[0]*M
C=[]
for m in range(M):
    A[m],B[m] = map(int, input().split())
    C.append(list(map(int, input().split())))

keys=[[] for i in range(N)]
keys_num=[0]*N
for i,c_list in enumerate(C):
    for c in c_list:
        keys[c-1].append(i+1)
        keys_num[c-1]+=1
if min(keys_num)==0:
    print(-1)
    exit()
    
    

bought=[]
ans=0
while len(keys_num)>0:
    i=keys_num.index(min(keys_num))
    K=keys[i]
    index=min(K,key=lambda k:A[k-1])
    if index in bought:
        pass
    else:
        ans+=A[index-1]
        bought.append(index)
    keys.pop(i)
    keys_num.pop(i)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N,M = list(map(int, readline().split()))

aaa = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, readline().split()))
    c = list(map(int, readline().split()))
    for j in range(b):
        aaa[c[j]-1].append(a)

for i in range(N):
    aaa[i].sort()

# print(aaa)

used = []
ans = 0
for i in range(N):
    if len(aaa[i]) == 0:
        ans = -1
        break
    if aaa[i][0] not in used:
        used.append(aaa[i][0])
        ans += aaa[i][0]

print(ans)

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())
    INF = int(1E8)
    dp = [INF for _ in range(2**N)]
    A = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        ind = 0
        for c in C:
            A[c-1].append(a)
            ind += 2**(c-1)
        dp[ind] = min(dp[ind], a)

    Id = [i for i in range(2**N)]
    Id.sort(key=lambda x: bin(x).count('1'))

    for x in Id:
        bitx = list(bin(x)[2:])
        l = len(bitx)
        for i in range(l):
            if bitx[l-1-i] == '1':
                for a in A[i]:
                    dp[x] = min(dp[x-2**i]+a, dp[x])
    if dp[2**N-1] >= INF:
        print(-1)
    else:
        print(dp[2**N-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m, *abc = map(int, open(0).read().split())

    a = {}
    c = {}
    for i in range(n):
        c[i] = []
    init = 0
    for i in range(m):
        _a = abc[init]
        _b = abc[init+1]
        _c = [j-1 for j in abc[init+2:init+2+_b]]
        init = init + 2 + _b
        a[i] = [_a, _c]
        for __c in _c:
            c[__c].append(i)

    for _c in c.values():
        if len(_c) == 0:
            print(-1)
            return()

    cost = 0
    while c:
        for key, _c in c.items():
            if len(_c) == 1:
                _a = a.pop(key)
                cost += _a[0]
                rem = _a[1]
                for _rem in rem:
                    del c[_rem]
                break
        else:
            break


    for key, _c in c.items():
        min_cost = 10**6
        for __c in _c:
            min_cost = min(min_cost, a[__c][0])
        cost += min_cost
    ans = cost
    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
sum=0
a=[0]*m
b=[0]*m
c=[0]*m
hako=[i+1 for i in range(n)]
for i in range(m):
	a[i],b[i] = map(int, input().split())
	c[i]=list(map(int, input().split()))
for i in range(m):
	count=0
	for j in range(b[i]):
		if hako[c[i][j]-1]!=0:
			hako[c[i][j]-1]=0
			count+=1
	if count!=0:
		sum+=a[i]
print(sum)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
keys = [0]*M
for i in range(M):
    a,b = map(int,input().split())
    c = set(map(lambda x: int(x)-1,input().split()))
    keys[i] = (a,c)

o = list(range(2**N))
o[0] = (0,set())
for i in range(1,2**N):
    p = []
    for need_open,dpminus in list(
            map(lambda x:(x, i ^ (1 << x)),
                filter(lambda x:(i >> x) & 1,range(N))
            )
        ):
        if o[dpminus] == -1:
            continue
        price,opened = o[dpminus]
        if need_open in opened:
            p.append((price,opened))
        else:
            hogehoge = list(filter(lambda x:need_open in x[1],keys))
            if len(hogehoge):
                new_key = min(hogehoge)
                p.append((price + new_key[0],opened | new_key[1]))
    if len(p):
        o[i] = min(p)
    else:
        o[i] = -1

if o[-1] == -1:
    print(-1)
else:
    print(o[-1][0])

Submission status: Wrong Answer

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

N, M = map(int, input().split())
key_dict = {}
for i in range(1, N + 1):
    key_dict[i] = []

# print(key_dict)

keys = []

for i in range(M):
    price, b = map(int, input().split())
    key_nums = list(map(int, input().split()))
    for key in key_nums:
        key_dict[key].append(price)
    keys.append(key_nums)


sorted_keys = sorted(key_dict.items(), key=lambda x: len(x[1]))
# print(sorted_keys)


total = 0
done = []
for k, v in sorted_keys:
    if len(v) == 0:
        print(-1)
        quit()
#     print("done")
#     print(done)
    if k not in done:
#         print(min(v))
        total += min(v)

        for i in keys[k - 1]:
#             print("購入済みの鍵:{}".format(i))
            done.append(i)

print(total)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a_list = []
b_list = []
c_list = []
for _ in range(M):
    a, b = map(int,input().split())
    c = list(map(int,input().split()))
    c = [cc-1 for cc in c]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)


takara_keys = {}
for i in range(N):
    takara = []
    for idx, c in enumerate(c_list):
        if i in c:
            takara.append(idx)
    takara_keys[i] = takara

clear = [1 for _ in range(N)]
def dp(memos, cost):
    if memos == clear:
        return cost
    costs = [10**9]
    for takara, memo in enumerate(memos):
        if memo == 0:
            next_keys = takara_keys[takara]
            for key in next_keys:
                tmp_memos = memos[:]
                for takara_idx in c_list[key]:
                    tmp_memos[takara_idx] = 1
                tmp_cost = cost + a_list[key]
                costs.append(dp(tmp_memos,tmp_cost))
        break
    return min(costs)

length_0_flag = False
for v in takara_keys.values():
    if len(v)==0:
        length_0_flag = True

if length_0_flag:
    print(-1)
else:
    print(dp([0 for _ in range(N)],0))

Submission status: Wrong Answer

Solution code:
import math
import fractions
from collections import Counter
import heapq
from collections import defaultdict
from heapq import heappop, heappush

def read():
    return int(input())

def readmap():
    return map(int, input().split())

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

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

# def is_valid(s, k):
#     return s & k == k

# def func(dp, s, key, cost):
#     min_cost = INT_MAX
#     for k, c in zip(key, cost):
#         if is_valid(s, k):
#             min_cost = min(min_cost, c + dp[s - k])
#     return min_cost

if __name__ == "__main__":
    N, M = readmap()
    key = [0] * M
    cost = [0] * M

    all_key = set()

    for i in range(M):
        a, b = readmap()
        C = set(readlist())
        key[i] = sum([1<<(bit-1) for bit in C])
        cost[i] = a
        all_key = all_key.union(C)

    if all_key != set(range(1, N+1)):
        print(-1)
        quit()

    edges = []
    for k, v in zip(key, cost):
        for s in range((1<<N) - 2):
            src = s
            dst = s | k
            if src != dst:
                edges.append((src, dst, v))
    

    # dp[0] = 0
    # for s in range(1, (1<<N) + 1):
    #     dp[s] = func(dp, s, key, cost)
    
    # print(dp[(1<<N) - 1])
    g = Graph()
    for src, dst, weight in edges:
        g.add_edge(src, dst, weight)
    
    d = Dijkstra(g, 0)
    print(d.shortest_distance((1<<N) - 1))

Submission status: Wrong Answer

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

keys_dic = {}
treasures_list = [[] for x in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    c = [int(x) for x in input().split()]
    keys_dic[i+1] = a
    for treasure in c:
        treasures_list[treasure-1].append(i+1)


ok = 10**8
ng = 0

def can_open_all_treasure(money):
    total_cost = 0
    for treasures in treasures_list:
        used_keys = []
        if len(treasures) == 0:
            print(-1)
            exit()
        else:
            min_cost = 10**6
            for openable_key in treasures:
                if openable_key not in used_keys:
                    pass
                else:
                    min_cost = min(keys_dic[openable_key], min_cost)
                total_cost += min_cost
                used_keys.append(openable_key)

    if money >= total_cost:
        return True
    else:
        return False

while ok - ng > 1:
    mid = (ok + ng) / 2
    if can_open_all_treasure(mid):
        ok = mid
    else:
        ng = mid

if ok <= 1 or ok >= 10 ** 8:
    print(-1)
else:
    print(int(ok))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M = LI()
    key_for = [[] for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        C = LI_()
        keys = set()
        for c in C:
            keys.add(c)
        for i in range(N):
            if i in C:
                key_for[i].append([a,keys])

    for i in range(N):
        if key_for[i] == []:
            return(-1)
        key_for[i].sort(key=lambda x:x[0])

    crt = [[0,set()]]
    for i in range(N):
        nxt = []
        for crt_a,crt_keys in crt:
            for nxt_a,nxt_keys in key_for[i]:
                if nxt_keys <= crt_keys:
                    continue
                nxt.append([nxt_a+crt_a,nxt_keys|crt_keys])
        crt = [x for x in nxt]

    crt.sort(key=lambda x:x[0])
    for a,keys in crt:
        if len(keys)==N:
            return(a)

    return(-1)

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
import os

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, b = map(int,input().split())
    A[i] = a
    B[i] = b
    C.append(list((map(int,input().split()))))
dp = [[0 for _  in range(sum(A))] for _ in range(M)]
miniC = sum(A)+1
open = set()
for i in range(M-1):
    for c in range(sum(A)-1):
        if c >= A[i]:
            open = open.union(C[i])
            dp[i+1][c] = max(dp[i][c-A[i]]+len(open),dp[i][c])
        else:
            dp[i+1][c] = dp[i][c]
        if dp[i+1][c] == N:
            miniC = min(miniC,c)
if miniC > sum(A):
    print(-1)
else:
    print(miniC)

Submission status: Wrong Answer

Solution code:
print("＼( 'ω')／")

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    for x in list(itertools.permutations(c)):
        l0 = [slice(None)]*n
        l1 = [slice(None)]*n
        for y in x:
            l0[y-1] = 0
            l1[y-1] = 1
            dp[tuple(l1)] = np.minimum(dp[tuple(l0)] + a, dp[tuple(l1)])
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

keys_dic = {}
treasures_list = [[] for x in range(n)]
print(treasures_list)

for i in range(m):
    a, b = map(int, input().split())
    c = [int(x) for x in input().split()]
    keys_dic[i+1] = a
    for treasure in c:
        treasures_list[treasure-1].append(i+1)


ok = 10**8
ng = 0

def can_open_all_treasure(money):
    total_cost = 0
    for treasures in treasures_list:
        used_keys = []
        if len(treasures) == 0:
            print(-1)
            exit()
        else:
            min_cost = 10**6
            for openable_key in treasures:
                if openable_key not in used_keys:
                    pass
                else:
                    min_cost = min(keys_dic[openable_key], min_cost)
                total_cost += min_cost
                used_keys.append(openable_key)

    if money >= total_cost:
        return True
    else:
        return False

while ok - ng > 1:
    mid = (ok + ng) / 2
    if can_open_all_treasure(mid):
        ok = mid
    else:
        ng = mid

if ok <= 1 or ok >= 10 ** 8:
    print(-1)
else:
    print(int(ok))

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
dp=[10**18]*(2**(n))
ll=[0]*(n+1)
for i in range(m):
    x,y=[int(j) for j in input().split()]
    tmp=set([int(j) for j in input().split()])
    for j in tmp:
        ll[j]=1
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind+=2**(j-1)
    dp[ind]=x
if sum(ll)!=n:
    print(-1)
    exit()

for i in range(1,2**n):
    for j in range(i+1,2**n):
        dp[i|j]=min(dp[i|j],dp[i]+dp[j])

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = []
for i in range(m):
  a, b = map(int, input().split())
  l += list(map(int, input().split()))
for i in range(n):
  if (i+1) not in l:
    print(-1)
    quit()
print(1)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = []
B = []
C = []
for _ in range(M):
    ab = [int(x) for x in stdin.readline().rstrip().split()]
    A.append(ab[0])
    B.append(ab[1])
    C.append([int(x) for x in stdin.readline().rstrip().split()])

opened = [False] * N
keys = [False] * M


def dfs(op, c, k):
    if False not in op:
        return c
    if False not in keys:
        return 10 ** 10
    output = 10 ** 10
    for n in range(M):
        if not k[n]:
            kk = k
            kk[n] = True
            opp = op
            for x in C[n]:
                opp[x - 1] = True
            output = min(output, dfs(opp, c + A[n], kk))
    return output


ans = dfs(opened, 0, keys)
if ans == 10 ** 10:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
[N,M] = list(map(int,input().split()))
A = []
B = []
C = [[0] * N for i in range(M)]
for i in range(M):
    [tmpA,tmpB] = list(map(int,input().split()))
    A.append(tmpA)
    B.append(tmpB)
    for j in list(map(int,input().split())):
        C[i][j-1]=1

minmin = [10**7]*(N+1)
minmin[0] = 0
cand = [10**7]*N
t=1
flag = 1
out=0
while t < N+1:
    if flag == 0:
        out = -1
    flag = 0
    for i in range(M):
        prod=1
        if C[i][t-1]==1:
            s = 0
            cand[t-1]=C[i][t-1]*A[i]+minmin[t-1]
            while s <t-1:
                prod *= C[i][s]*minmin[s]
                s+=1
            cand[t-1] += prod*minmin[s]*(-1)
            flag = 1
        if cand[t-1] < minmin[t]:
            minmin[t] = cand[t-1]
    t+=1

if out==-1:
    print(-1)
else:
    print(minmin[-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    
    li = list(map(int, input().split()))
    li2 = list(map(int, input().split()))    
    a.append([li,li2])

b = []
c = ["0"]*n
from collections import defaultdict
d = defaultdict(int)
for i in range(n):
    b.append(i+1)


for i in range(len(a)):
    
    for j in range(1,n+1):
        
        if j in a[i][1]:
            min1 = int(a[i][0][0])
            d[j] = min(min1,int(a[i][0][0]))
            
sum = 0

for v in d.values():
    sum += v

Submission status: Wrong Answer

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    ABC = []
    sum_val_b = 0
    for i in range(M):
        a, b = (int(j) for j in input().split())
        c = [int(j) for j in input().split()]
        sum_val_b += b
        ABC.append((a,b,c))
    ABC.sort(key=lambda x: x[1])
    if sum_val_b < N:
        print(-1)
        return 0
    r = [float('inf')] * (N+1)
    keys = [False] * N
    r[0] = 0
    for i in range(1,N+1):
        q = r[i]
        insurance = -1
        for j in range(M):
            if i - ABC[j][1] < 0:
                break
            if (ABC[j][0] + r[i - ABC[j][1]]) < q:
                if insurance == -1:
                    insurance = j
                else:
                    if (ABC[j][0] + r[i - ABC[j][1]]) < (ABC[insurance][0] + r[i - ABC[insurance][1]]):
                        insurance = j
                flag = False
                for k in ABC[j][2]:
                    if keys[k-1] == False:
                        keys[k-1] = True
                        flag = True
                if flag:
                    q = (ABC[j][0] + r[i - ABC[j][1]])
        if q == float('inf'):
            q = (ABC[insurance][0] + r[i - ABC[insurance][1]])
        r[i] = q
    print(r[N])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ac=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    ac.append([a,c])
ac.sort()
already_opened_box=[]
now_price=0
for i in range(m):
    not_opened=set(ac[i][1]).difference(set(already_opened_box))
    if(len(not_opened)>0):
        if(len(set(ac[i][1]).intersection(already_opened_box)) == len(already_opened_box)):
            now_price=ac[i][0]
            already_opened_box=ac[i][1]
        else:
            now_price+=ac[i][0]
            already_opened_box=set(already_opened_box).union(set(ac[i][1]))

    if(len(already_opened_box) >= n):
        break
if(len(already_opened_box) >= n):
    print(now_price)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N,M = map(int,input().split())
A = []
C = []
D = {i:0 for i in range(1,N+1)}

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

C = sorted(C, key=lambda x:x[0])

F = [0]*(len(C))

for i in range(len(C)-1) :
    ca = set(C[i][1])
    for j in range(i+1,len(C)) :
        cb = set(C[j][1])
        if cb.issubset(ca) :
            F[j] = 1

CC = []
for i in range(len(C)) :
    if F[i] == 0 :
        CC.append(C[i])

C = deepcopy(CC)

ans = 0
flg = 0
debug = []
for i in range(len(C)) :
    a,cx = C[i]
    dflg = 0
    for c in cx :
        if D[c] == 0 :
            dflg = 1
            D[c] = 1
            debug.append(a)
    if dflg :
        ans += a
for i in range(1,N+1) :
    if D[i] == 0 :
        print(-1)
        flg = 1
        break
if flg == 0 :
    print(ans)
#print(debug)

Submission status: Wrong Answer

Solution code:
num_box, num_key = map(int, input().split(' '))

by_box = {b: [] for b in range(1, num_box+1)}
by_fit = {}

for _ in range(1, num_key+1):
    cost, num_open = map(int, input().split(' '))
    unlock = tuple([int(x) for x in input().split(' ')])

    if unlock in by_fit.keys():
        former_cost = by_fit[unlock]
        if former_cost <= cost:
            continue
        else:
            for b in unlock:
                by_box[b].remove((former_cost, unlock))
                by_box[b].append((cost, unlock))
    else:
        for b in unlock:
            by_box[b].append((cost, unlock))

# print(by_box)
for b in range(1, num_box+1):
    if len(by_box[b]) == 0:
        print("-1")
        exit(0)
    by_box[b].sort()
# print(by_box)

# one-by-one
limit = 0
one_opened = set()
for b in range(1, num_box+1):
    if b in one_opened:
        continue
    cost, unlock = by_box[b][0]
    limit += cost
    one_opened = one_opened.union(unlock)

print(limit)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
box = [100001]*n
samp = [100001]*n
number = [0]*n
value = 0
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    for j in range(b):
        samp[c[j]-1] = a
    for k in range(n):
        if box[k]>samp[k]:
            number[k]=i
        box[k] = min(box[k],samp[k])
if 100001 in box:
    print(-1)
else:
    for i in range(n):
        if box.count(box[i])>=2 and number[i:n+1].count(number[i])==1:
            value += box[i]
        elif box.count(box[i])==1:
            value += box[i]
    print(value)

Submission status: Wrong Answer

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


n, m = map(int, input().split())

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

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

memo = [0] * n
tmp = []

ans = 0

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

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

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

    l = len(tmp)
    x = []
    for j in range(l):
        if (1 << j) & bit_max:
            x.append(tmp[j])
            for t in box[tmp[j]][1]:
                t -= 1
                memo[t] -= 1
    ans -= cost_max

    for d in x:
        tmp.remove(d)

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

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
N_list = []
for i in range(1, N+1):
    N_list.append(i)
A_B = []
A = []
B = []
C = []
a_b_dict = {}
for i in range(M):
    a,b = map(int, input().split())
    c = [int(e) for e in input().split()]
    c.insert(0, a)
    a_b_dict[a/b] = c

#print(a_b_dict)
a_b_dict_sorted = sorted(a_b_dict.items(), key=lambda x:x[0])
#print(a_b_dict_sorted)
count = 0
judge = 0
for item in a_b_dict_sorted:
    money = item[1][0]
    item[1].pop(0)
    count_j = False
    for del_ in item[1]:
        if del_ in N_list:
            N_list.remove(del_)
            count_j = True
    #print(N_list)
    if count_j == True:
        judge += money
    if len(N_list) == 0:
        break;
    count += 1

if len(N_list) != 0:
    print('-1')
else:
    print(judge)