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:
import sys
import collections
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(m*2)]

dic = {}

for i in range(len(a)):
    if i%2 == 0:
        continue
    if dic.get(tuple(a[i])):
        dic[tuple(a[i])] = min(dic[tuple(a[i])], a[i-1][0])
    else:
        dic[tuple(a[i])] = a[i-1][0]
starts = collections.defaultdict(list)
for key in dic:
    starts[key[0]].append((key,dic[key]))

def dfs(ansd,ons, cur):
    # print(ons)
    if sum(ons) == 0:
        ansd[0] = min(ansd[0], cur)
        return
    for i in range(len(ons)):
        if ons[i] == 1:
            # print(starts[i],i)
            for child in starts[i+1]:
                ons = copy.deepcopy(ons)
                for z in child[0]:

                    # print(child[0])
                    ons[z-1] = 0
                dfs(ans,ons,cur+child[1])
            break


ans = [float('inf')]
dfs(ans,[1]*(n),0)

print(ans[0]) if ans[0] != float('inf') else print(-1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
A = []
C = []
li = [[] for i in range(N+1)]

def flatten(nested_list):
    """2重のリストをフラットにする関数"""
    return [e for inner_list in nested_list for e in inner_list]

# 各宝箱を開けられる鍵の最安値のリストを作成（最大12コ）。
# そのあと重複を削除して最安を探す。

for key_num in range(M):
  a, _ = map(int, input().split())
  A.append(a)
  c = list(map(int, input().split()))
  C.append(c)
  for i in c:
    li[i].append([a, key_num + 1]) 

for i in range(1,N+1):
  li[i].sort()

#print(li)
  
cheepests = []
nullcnt = 0
for i in li:
  if not i:
    nullcnt += 1
  else:
#    print(i)
    cheepests.append(i[0][1])

if nullcnt > 1:
  print(-1)
  exit()
  
# print(nullcnt)
# print(cheepests)

set_cheepests = list(set(cheepests))

#重複削除の処理
pr = 10 ** 10
for i in range(1, len(set_cheepests) + 1):
  ss = list(itertools.combinations(set_cheepests,i))
  boxs = []
  for j in ss:
    for jj in j:
      # print(jj)
      boxs.append(C[jj-1])
  fla_boxs = list(set(flatten(boxs))) 

  # print(fla_boxs)
  # print(list(range(1,N)))
  # print(fla_boxs == list(range(1,N)))

  if fla_boxs == list(range(1,N+1)):
    ppr = sum([A[i - 1] for i in set_cheepests])
    if pr > sum([A[i - 1] for i in set_cheepests]):
      pr = sum([A[i - 1] for i in set_cheepests])
  
print(pr)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(m*2)]

dic = {}

for i in range(len(a)):
    if i%2 == 0:
        continue
    if dic.get(tuple(a[i])):
        dic[tuple(a[i])] = min(dic[tuple(a[i])], a[i-1][0])
    else:
        dic[tuple(a[i])] = a[i-1][0]
starts = collections.defaultdict(list)
for key in dic:
    starts[key[0]].append((key,dic[key]))

def dfs(ansd,ons, cur):
    # print(ons)
    if sum(ons) == 0:
        ansd[0] = min(ansd[0], cur)
        return
    for i in range(len(ons)):
        if ons[i] == 1:
            # print(starts[i],i)
            for child in starts[i+1]:
                for z in child[0]:
                    ons = copy.deepcopy(ons)
                    # print(child[0])
                    ons[z-1] = 0
                dfs(ans,ons,cur+child[1])
            break


ans = [float('inf')]
dfs(ans,[1]*(n),0)

print(ans[0]) if ans[0] != float('inf') else print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()

a = []
a_app = a.append
b = []
b_app = b.append
c = []
c_app = c.append

# stands for key_price_id_dict
kpid = defaultdict(lambda: list())

for i in range(M):
    am, bm = read_int()
    cm = read_int()
    a_app(am)
    b_app(bm)
    c_app(cm)
    for key in c[i]:
        kpid[key].append([am, i])

INF = float('INF')

def solve():
    ans = 0
    # print(kpid)
    prev_key = []
    for i in range(1, N + 1):
        if len(kpid[i]) == 0:
            ans = -1
            break
        key = [INF, 0]
        for j in range(len(kpid[i])):
            if key[0] > kpid[i][j][0]:
                key = kpid[i][j]
            # 同じ値段の鍵 and 既に使っている
            elif key[0] == kpid[i][j][0] and kpid[i][j] in prev_key:
                key = kpid[i][j]
        # price = min(kpid[i][0])
        if key in prev_key:
            continue
        ans += key[0]
        prev_key.append(key)
    return ans

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

Submission status: Wrong Answer

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

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

  
  n,m = map(int, input().split())
  bps = [100007]*n
  keys = [0]*n
  kps = []
  for i in range(m):
    a,b = map(int,input().split())
    kps.append(a)
    for j in map(int,input().split()):
      if a/b < bps[j-1]:
        bps[j-1] = a/b
        keys[j-1] = i+1
  
  if 0 in keys:
    print(-1)
  else:
    ans = sum(kps[i-1] for i in set(keys))
    print(ans)
  
if __name__ == '__main__':
  solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
keys=[]
boxes=[0]*n
allsum=0
for i in range(m):
  a,b=map(int,input().split())
  targets=list(map(int,input().split()))
  allsum=allsum+a
  for j in range(len(targets)):
    targets[j]=targets[j]-1
    boxes[targets[j]]=boxes[targets[j]]+1
  keys.append([a,targets])

if 0 in boxes:
  print(-1)
else:
  newkeys=sorted(keys, key=lambda x: x[0],reverse=True)
  for i in range(len(newkeys)):
    tar=newkeys[i][1]
    ng=False
#    print(boxes)
    for j in range(len(tar)):
      if boxes[tar[j]]<2:
        ng=True
        break
    if ng!=True:
#      print(str(newkeys[i][0])+" is able to be deleted")
      allsum=allsum-newkeys[i][0]
#      print("allsum:"+str(allsum))
      for p in range(len(tar)):
        boxes[tar[p]]=boxes[tar[p]]-1
  print(allsum)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = []
C = []
S = set()
for j in range(M):
    a, b = map(int, input().split())
    A.append((j, a))
    c = list(map(int, input().split()))
    C.append(c)
    for i in c:
        S.add(i)
#print(C)      
if len(S) < N:
    print(-1)
    exit()
A.sort(key=lambda x: x[1])
boxes = set()
answer = []
for a in A:
    if len(set(C[a[0]]) - boxes) >= 1:
        answer.append(a[0])
        for z in C[a[0]]:
            boxes.add(z)
# answerは必要な鍵のリスト　ただ被りがある
answer2 = []
boxes2 = set()

for a in answer[::-1]:
    if len(set(C[a]) - boxes2) >= 1:
        answer2.append(a)
        for z in C[a]:
            boxes2.add(z)
count = 0
A.sort(key=lambda x: x[0])
for a in answer2:
    count += A[a][1]
#print(A)
#print(answer)
#print(answer2)
print(count)

Submission status: Wrong Answer

Solution code:
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])
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:
n,m = map(int,input().split())
dp=[10**5+1]*n

for i in range(m):
  a,b = map(int,input().split())
  c = list(map(int,input().split()))
  if dp[c[0]-1] >= a:
    dp[c[0]-1] = a
    for j in range(1,b):
      dp[c[j]-1] = 0
  
  
if 10**5+1 in dp :
  print("-1")
else:
  print(sum(dp))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

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

n, m = na()
cost = []
k = []
for i in range(m):
    a, b = na()
    cost.append(a)
    k.append(na())

kouho = [[] for _ in range(n)]
for i in range(1, n+1):
    for j in range(m):
        if i in k[j]:
            kouho[i-1].append(j)
used = []
ans = 0
for i in range(n):
    m = 10 ** 10
    if len(kouho[i]) == 0:
        ans = -1
        break
    tmp = []
    for k in kouho[i]:
        if cost[k] < m:
            m = cost[k]
            tmp = [k]
        if cost[k] == m:
            tmp.append(k)
    flag = False
    for num in tmp:
        if num in used:
            flag = True
            break
    if not flag:
        ans += m
        used.extend(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import fractions
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
a = []
b = []
c = []
for i in range(m):
    aa,bb = MAP()
    cc = LIST()
    for i in range(bb):
        cc[i] -=1
    a.append(aa)
    b.append(bb)
    c.append(cc)
clist = [[]for i in range(n)]

for i in range(m):
    for j in range(len(c[i])):
        clist[c[i][j]].append((i,a[i]))

for i in range(n):
    if len(clist[i]) == 0:
        print(-1)
        sys,exit()
    clist[i] = sorted(clist[i],key = lambda x:x[1])

res = []
for i in range(n):
    res.append(clist[i][0])

res = list(set(res))

ans = 0
for i in range(len(res)):
    ans += res[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
dp = [[int(2e8) for _ in range(2**n)] for _ in range(2)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(m):
    a, _ = map(int, input().split())
    k = sum(map(lambda c: 1 << (c - 1), list(map(int, input().split()))))
    for j in range(2**n):
         dp[(i + 1) % 2][j | k] = min([dp[i % 2][j | k], dp[(i + 1) % 2][j | k], dp[i % 2][j] + a])
ans = min(dp[0][-1], dp[1][-1])
if int(1e8) < ans:
    ans = -1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import sys
import collections
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(m*2)]

dic = {}

for i in range(len(a)):
    if i%2 == 0:
        continue
    if dic.get(tuple(a[i])):
        dic[tuple(a[i])] = min(dic[tuple(a[i])], a[i-1][0])
    else:
        dic[tuple(a[i])] = a[i-1][0]
starts = collections.defaultdict(list)
for key in dic:
    starts[key[0]].append((key,dic[key]))

def dfs(ansd,ons, cur):
    # print(ons)
    if sum(ons) == 0:
        ansd[0] = min(ansd[0], cur)
        return
    for i in range(len(ons)):
        if ons[i] == 1:
            # print(starts[i],i)
            for child in starts[i+1]:
                for z in child[0]:
                    ons = copy.deepcopy(ons)
                    # print(child[0])
                    ons[z-1] = 0
                dfs(ans,ons,cur+child[1])
            break


ans = [float('inf')]
dfs(ans,[1]*(n),0)
# print(starts)
print(ans[0]) if ans[0] != float('inf') else print(-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a_b = []
c_li = []
ans_li = []

for i in range(m):
  a,b = map(int,input().split())
  a_b.append([a,b])
  c = list(map(int,input().split()))
  c_li.append(c)
print(a_b,c_li)
for i in range(2**m):
  group = []
  total = 0
  for j in range(m):
    if((i>>j)&1):
      group = group + c_li[j]
      total += a_b[j][0]
  group = set(group)
  if len(group)==n:
    ans_li.append(total)
if len(ans_li) >0:
  print(min(ans_li))
else:
  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()])

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

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


def dfs(op, c, k):
    if False not in op:
        return c
    output = 10 ** 7
    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 ** 7:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
import sys
input=sys.stdin.readline
D=dict()
x=[0 for i in range(N)]
#print(x)
x=tuple(x)
D[x]=0
#print(D)
for i in range(M):
    d=dict()
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    L=[0 for x in range(N)]
    for j in range(b):
        L[c[j]-1]=1
    for k in D.items():
        if k[0] not in d:
            d[k[0]]=k[1]
        else:
            if d[k[0]]>k[1]:
                d[k[0]]=k[1]
        x=[0 for x in range(N)]
        for l in range(N):
            if k[0][l]+L[l]>0:
                x[l]=1
        if tuple(x) in D:
            if D[tuple(x)]>a+k[1]:
                if tuple(x) in d:
                    if d[tuple(x)]>a+k[1]:
                        d[tuple(x)]=a+k[1]
                else:
                    d[tuple(x)]=a+k[1]
        else:
            d[tuple(x)]=a+k[1]
    D=d
    #print(D)
#print(D)
X=[1 for i in range(N)]
if tuple(X) in D:
    print(D[tuple(X)])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import copy

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

lis = [-1]*n
cost = 0
temp = [-1]*n
cost_temp = 0
possible = False
for i in range(m):
  for j in C[i]:
    temp[j]= i
  tt = list(set(temp))
  if -1 in tt :
    tt.remove(-1)
  for t in tt:
    cost_temp += A[t]
  if cost_temp <= cost or not possible :
    lis = copy.copy(temp)
    cost = cost_temp
  else:
    temp = copy.copy(lis)
  cost_temp =0
  if -1 not in lis:
    possible = True

if possible:
  print(cost)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

keymap = [[0] * m for _ in range(n)]
prices = []
for j in range(m):
    a, b = list(map(int, input().split()))
    cs = list(map(int, input().split()))
    prices.append(a)
    for c in cs:
        keymap[c - 1][j] = 1

# print(keymap)
# print(prices)

costs = []
for i in range(n):
    ki = keymap[i]
    nonzeros = []
    for j in range(m):
        if ki[j] != 0:
            nonzeros.append((j, prices[j]))

    costs.append(min(nonzeros, key=itemgetter(1)) if len(nonzeros) > 0 else 0)

# print(costs)

keys = set()
if 0 in costs:
    print(-1)
else:
    goukei = 0
    for key, value in costs:
        if key not in keys:
            goukei += value
            keys.add(key)
    print(goukei)

Submission status: Wrong Answer

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

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

  
  n,m = map(int, input().split())
  bps = [100007]*n
  keys = [0]*n
  kps = []
  for i in range(m):
    price, _ = map(int,input().split())
    kps.append(price)
    for j in map(int,input().split()):
      if price < bps[j-1]:
        bps[j-1] = price
        keys[j-1] = i+1
  
  if 0 in keys:
    print(-1)
  else:
    ans = sum(kps[i-1] for i in set(keys))
    print(ans)
  
if __name__ == '__main__':
  solve()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
from itertools import combinations
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

def subsets(items):
    _subsets_=[]
    for i in range(len(items) + 1):
        for c in combinations(items, i):
            _subsets_.append(c)
    return _subsets_

INF = 999999999999999999999999

n,m = get_nums_l()

keys = [INF] * (2 ** (n+2))

for _ in range(m):
    cost, b = get_nums_l()
    ccc = get_nums_l()

    #print(cost,b)


    for s in subsets(ccc):
        keyn = 0
        #print(s)
        for c in s:
            keyn += 2 ** c
        
        #print("keyn", keyn)
        if keys[keyn] > cost:
            keys[keyn] = cost

for i in range(1,n+1):
    if keys[2**i] == INF:
        print(-1)
        exit()

memo=[None] * (2 ** (n+2))

def solve(targets):
    
    #print(targets)

    if len(targets) == 0:
        return 0

    if len(targets) == 1:
        return keys[2*list(targets)[0]]

    all_s = set(targets)

    keyn=0
    for c in targets:
        keyn += 2 ** c
    
    if memo[keyn]:
        return memo[keyn]

    _min = keys[keyn]

    for s in subsets(targets):
        if len(s) == 0 or len(s) == len(targets):
            continue
        rev = all_s.difference(s)
        cost = solve(s) + solve(rev)
        if _min > cost:
            _min = cost
    memo[keyn] = _min
    return _min

ans = solve(set(range(1, n+1)))
print(ans if ans < INF else -1)

Submission status: Wrong Answer

Solution code:
#E

#D
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))'''
# 行数

'''
N = int(input().strip())

# 2次元配列
grid = []
for i in range(N):
    array = list(map(int, input().strip().split()))
    grid.append(array)
'''

import numpy as np
n, m = map(int, input().split())

A = []
B = []
C = []

w = np.zeros((n+1,m+1))

MAX = 10**5 + 1
for i in range(n+1):
    for j in range(m+1):
        w[i][j] = MAX

#print(w)

for i in range(m):

    #a cost
    #c list of box
    a,b = map(int, input().split())
    c = list(map(int, input().strip().split()))

    A.append(a)
    C.append(c)

    for j in range(b):
        w[c[j]][i] = a

#print(w)
ans = np.zeros((n+1))
cov = np.zeros((n+1))
cov[0] = 1
final_ans = -1
for i in range(1,n+1):
    #print('step : ',i)
    dex = w[i,:].argmin()
    ans[i] = w[i][dex]
    #print('dex : ',dex)
    #print('ans : ',ans)
    #print('C :',C[dex])
    for j in range(len(C[dex])):
        cov[C[dex][j]] = 1
    #print('cov : ',cov)
    if sum(cov) == n+1:
        final_ans = sum(ans)
        break

print(int(final_ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split(" "))
keys = []

def toInt(x):
    x = [1 if any([y-1 == i for y in x]) else 0 for i in range(12)][::-1]
    # print(x)

    ans = 0
    for bit in x:
        ans = (ans << 1) | bit
    return ans

for i in range(m):
    a, b = map(int, input().split(" "))
    cs = list(map(int, input().split(" ")))
    keys.append((a, toInt(cs), cs))

keys = sorted(keys, key=lambda x: (len(x[2]), x[0]))
costs, items, _ = zip(*keys)

taken = 0
used = set()
for i in range(len(keys)):
    diff = costs[i]

    if (taken | items[i]) > taken:
        used.add(i)
        taken = taken | items[i]
        # print("Take", costs[i])
        diff = 0


    diffk = set()
    for j in used:
        if i != j and (items[i] | items[j]) == items[i]:
            diffk.add(j)

    if sum([costs[j] for j in diffk]) > diff:
        used = used - diffk
        used.add(i)
        # print("Drop", [costs[j] for j in diffk])

if taken == int(2 ** n - 1):
    print(sum([costs[i] for i in used]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()

a = []
a_app = a.append
b = []
b_app = b.append
c = []
c_app = c.append

# stands for key_price_id_dict
kpid = defaultdict(lambda: list())

for i in range(M):
    am, bm = read_int()
    cm = read_int()
    a_app(am)
    b_app(bm)
    c_app(cm)
    for key in c[i]:
        kpid[key].append([am, i])

INF = float('INF')

def solve():
    ans = 0
    # print(kpid)
    prev_key = []
    for i in range(1, N + 1):
        if len(kpid[i]) == 0:
            ans = -1
            break
        key = [INF, 0]
        for j in range(len(kpid[i])):
            if key[0] > kpid[i][j][0]:
                key = kpid[i][j]
        # price = min(kpid[i][0])
        if key in prev_key:
            continue
        ans += key[0]
        prev_key.append(key)
    return ans

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m=map(int,input().split())

dic=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    c=[int(k) for k in input().split()] 
    dic[a]=c
dic=sorted(dic.items(), key=lambda x:x[0])

ans=0

dp=[0]*(n+1)

for i,j in dic:
    for k in j:
        if dp[k]==0:
            for l in j:
                dp[l]=i
            ans+=i
            break
        else:
            continue
    else:
        if ans<=i:
            continue
        else:
            ans=i
for i in range(1,n+1):
    if dp[i]==0:
        ans=-1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
box = [[-1, 0] for i in range(n)]
abc = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    abc.append([a, b] + c)
abc = sorted(abc, key=itemgetter(1))
for i in range(m):
    a = abc[i][0]
    b = abc[i][1]
    c = abc[i][2:]
    count = 0
    hikaku_key = set()
    flag = False
    for j in c:
        j -= 1
        if box[j][0] == -1:
            flag = True
        elif box[j][0] not in hikaku_key:
            count += box[j][1]
            hikaku_key.add(box[j][0])
    if a < count:
        flag = True
    if flag:
        for j in c:
            j -= 1
            box[j][0] = i
            box[j][1] = a
ans = 0
key = set()
for i in box:
    if i[0] == -1:
        print(-1)
        exit()
    if i[0] not in key:
        ans += i[1]
        key.add(i[0])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
data = []
for _ in range(M):
    a, b = map(int, input().split())
    C = {int(x) for x in input().split()}
    data.append([a, b, C])
data.sort()

opened = set()
i = 0
ans = 0
while opened != set(range(1, N + 1)):
    if not data[i][2] <= opened:
        ans += data[i][0]
        opened = opened | data[i][2]
    i += 1
    if i == M:
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))

dp=[-1]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            dp[j]=min(dp[j],a[i])
for i in range(m):
    for j in range(2**n):
        if dp[j]<0:
            continue
        if dp[c[i]|j]<0:
            dp[c[i]|j]=dp[j]+a[i]
        else:
            dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
c=[0]*(2000)
dp=[10**19]*(n+1)
from collections import defaultdict
d=defaultdict(list)
dp[0]=0 
for i in range(m): 
    c[i],k=map(int,input().split())
    z=[int(x) for x in input().split()]
    for x in z:
        d[i].append(x)
c=[[c[i],i]for i in range(m)]
c.sort()
for i in range(m):
    curr=c[i][0]
    ind=c[i][1]
    f=1 
    for x in d[ind]:
        if dp[x]==10**19:
            f=0 
    if f==0:
        cost=0 
        
        for x in d[ind]:
            dp[x]=curr
sm=set()
for i in range(1,n+1):
    if dp[i]==10**19:
        f=0 
    sm.add(dp[i])
if f==0:
    print(-1)
else:
    print(sum(sm))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
INF = float('inf')
V = [INF] * (1<<N)
V[0] = 0
for i in range(M):
    v,_ = map(int,input().split())
    b = 0
    s = list(map(int,input().split()))
    for a in s:
        b |= (1<<(a-1))
    V[b] = min(V[b], v)

vbs = []
for b,v in enumerate(V):
    if v==INF: continue
    vbs.append((v,b))

for r in range(1,len(vbs)):
    v1,b1 = vbs[r]
    for l in range(r):
        v2,b2 = vbs[l]
        V[b1|b2] = min(V[b1|b2], V[b1]+V[b2])

print(V[-1] if V[-1] < INF else -1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
box = [[-1, 0] for i in range(n)]
abc = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    abc.append([a, b] + c)
abc = sorted(abc, key=itemgetter(1))
for i in range(m):
    a = abc[i][0]
    b = abc[i][1]
    c = abc[i][2:]
    count = 0
    hikaku_key = set()
    flag = False
    for j in c:
        j -= 1
        if box[j][0] == -1:
            flag = True
        elif box[j][0] not in hikaku_key:
            count += box[j][1]
            hikaku_key.add(box[j][0])
    box_set = set()
    for j in list(hikaku_key):
        for k in range(n):
            if box[k][0] == j:
                box_set.add(k + 1)
    if box_set <= set(c):
        if a < count:
            flag = True
        if flag:
            for j in c:
                j -= 1
                box[j][0] = i
                box[j][1] = a
ans = 0
key = set()
for i in box:
    if i[0] == -1:
        print(-1)
        exit()
    if i[0] not in key:
        ans += i[1]
        key.add(i[0])
print(ans)

Submission status: Wrong Answer

Solution code:
def view():
    global keyboxes
    for keybox in keyboxes:
        for key in keybox:
            print(key.value,key.cans)
        print()

class Key():
    def __init__(self,value,cans):
        self.value=value
        self.cans=cans
    
    def __eq__(self,other):
        return self.value==other.value
    
    def __lt__(self,other):
        return self.value<other.value
    
    def __gt__(self,other):
        return self.value>other.value
    
N,M=map(int,input().split())
keys=[]
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    cans=[False for i in range(N)] # 宝箱の番号は0-イニシャルで扱う
    for i in c:
        cans[i-1]=True
    keys.append(Key(a,cans))

keyboxes=[[] for i in range(N)]
for key in keys:
    for i in range(N):
        if key.cans[i]:
            keyboxes[i].append(key)
            break

for keybox in keyboxes:
    keybox.sort()

opend=[False for i in range(N)]
ans=0
flag=True # 全ての宝箱を空けることができるか

#view()

for i in range(N):
    if not opend[i]:
        if keyboxes[i]==[]:
            flag=False
            break
        else:
            key=keyboxes[i][0]
            ans+=key.value
            for i in range(N):
                opend[i]=opend[i] or key.cans[i]

print(ans if flag else -1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
k=[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  k.append(tuple(map(int,input().split())))
a.append(0)
x=[-1]*n
for _ in range(m):
  for i in range(m):
    y=x[:]
    for j in k[i]:y[j-1]=i
    if x.count(-1)>y.count(-1):x=y[:];continue

    be=af=0
    for j in set(x):be+=a[j]
    for j in set(y):af+=a[j]
    if be>af:x=y[:]
if -1 in x:print(-1)
else:print(min(be,af))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a_list = []
#b_wa_list = [0]
all_key_list = []
each_key_list = []
a_sum = 0
for m in range(M):
    a,b = map(int,input().split())
    a_sum += a
    a_list.append([a,m])
#    b_wa_list.append(b_wa_list[-1]+b)
    key_list = list(map(int,input().split()))
    all_key_list.extend(key_list)
    each_key_list.append(key_list)
#all_key_list.append(0)
a_list.sort(reverse=True)

import copy

ex_ans = 0
is_ok = False
for i in range(M):
    mm = a_list[i][1]
    ex_key_list = copy.deepcopy(all_key_list)
    for k in range(len(each_key_list[mm])):
        ex_key_list.remove(each_key_list[mm][k])
#    ex_key_list = all_key_list[0:b_wa_list[mm-1]].extend(all_key_list[b_wa_list[mm]+1:])
    if len(list(set(ex_key_list))) == N:
        ex_ans += a_list[i][0]
        all_key_list = ex_key_list
        is_ok = True
    
if is_ok:
    print(a_sum - ex_ans)
else:
    print('-1')