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
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 += tmp
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]=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())
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 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:
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:
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[:]
  print(x)
if -1 in x:print(-1)
else:print(min(be,af))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

t = set([v for v in range(1, N + 1)])
L = [None] * M
for i in range(M):
    A, B, = map(int, input().split())
    C = [int(v) for v in input().split()]
    
    L[i] = (A, C)
    t = t - set(C)

if len(t) > 0:
    print(-1)
    exit()

ans = 10 ** 18
for i in range(1, 1 << N):
    t = set()

    for j in range(N):
        if (i >> j) & 1:
            t.add(j)

    m = set([v for v in range(1, N + 1)])
    score = 0
    for p in t:
        a = L[p]
        score += a[0]
        m = m - set(a[1])

    if len(m) == 0:
        ans = min(ans, score)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

# N = int(input())
# A = list(map(int, input().split()))
N, M = map(int, input().split())

cost = defaultdict(lambda: float('inf'))

for i in range(M):
    tmp = int(input().split()[0])
    cost[sum([2 ** (n-1) for n in map(int, input().split())])] = tmp

for _ in range(N):
    keys = list(cost.keys())
    n = len(keys)
    for i in range(n):
        for j in range(i+1, n):
            cost[keys[i]|keys[j]] = min(cost[keys[i]|keys[j]], cost[keys[i]] + cost[keys[j]])

ans = cost[sum([2 ** (n-1) for n in range(1, N+1)])]

print(ans if ans < float('inf') else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())

ac = []
ret = float('inf')
for _ in range(M) :
    a, b = map(int, input().split())
    c = 0
    for i in input().split() :
        c |= 1 << (int(i) - 1)
    if c == (1 << N) - 1 :
        ret = min(ret, a)
        continue
    ac.append([a, c])

ac.sort(reverse = True)
while ac :
    # for a, c in ac :
        # print(a, bin(c))
    # print()
    a, c = ac.pop()        
    ac_ = []
    
    for i in range(len(ac)) :
        ac[i][0] += a
        ac[i][1] |= c
        
        if ac[i][1] != (1 << N) - 1 :
            ac_.append(ac[i])
        else :
            ret = min(ret, ac[i][0])
    ac = ac_

if ret == float('inf') :
    print(-1)
else :
    print(ret)

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
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 = 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)):
    if (taken | items[i]) > taken:
        used.add(i)
        taken = taken | items[i]
        # print("Take", costs[i])

    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]) > costs[i]:
        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:
n,m = map(int,input().split())
box = [100001]*n
samp = [100001]*n
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):
        box[k] = min(box[k],samp[k])
if 100001 in box:
    print(-1)
else:
    print(sum(set(box)))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
price = []
Num = {}
total = 0
for i in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    price.append([-a, c])
    total += a
    for j in c:
        if j not in Num:
            Num[j] = 1
        else:
            Num[j] += 1

price.sort()
flag = [0]*N
if len(Num) != N:
    print(-1)
    exit()

for i in range(N):
    if Num[i+1] == 1:
        flag[i] = 1

for i in range(M):
    cnt = 0
    for j in price[i][1]:
        if flag[j-1] == 1:
            cnt += 1
    if cnt == 0:
        for j in price[i][1]:
            Num[j] -= 1
            if Num[j] == 1:
                flag[j-1] = 1
        total += price[i][0]
print(total)

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:
        for x in d[ind]:
            dp[x]=min(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())
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):
    dp[c[i]]=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())
box = [100001]*n
samp = [100001]*n
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):
        box[k] = min(box[k],samp[k])
    print(box)
if 100001 in box:
    print(-1)
else:
    print(sum(set(box)))

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
c=[]
a=[]
l=[[] for i in range(n+1)]
dp=[10**18]*(2**(n))
for i in range(m):
    x,y=[int(j) for j in input().split()]
    a.append(x)
    tmp=set([int(j) for j in input().split()])
    c.append(tmp)
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind+=2**(j-1)
    dp[ind]=x

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())
e = [[int(i) for i in input().split()] for i in range(m*2)] 

dct = {i+1 : 100001 for i in range (n)}
for i in range(m):
  a = e[i*2][0]
  b = e[i*2][1]
  c = e[i*2+1]
  
  for j in range(b):
    dct[c[j]] = min(dct[c[j]], a)
    
if 100001 in list(set(dct.values())):
  print(-1)
else:
  print(sum(list(set(dct.values()))))

Submission status: Wrong Answer

Solution code:
import math
A,B =map(int,input().split())

all_cost = [0 for _ in range(B)]
open_boxes = [[] for _ in range(B)]
boxes_num = [0 for _ in range(B)]

all_boxes = set()

for i in range(B):
    all_cost[i],boxes_num[i] = map(int,input().split())
    open_boxes[i] = list(map(int,input().split()))
    all_boxes = all_boxes | set(open_boxes[i])
    

import numpy as np
all_boxes_dict = dict()
for i,one in enumerate(all_boxes):
    all_boxes_dict[one] = i
    
program_viewers_np = []
for one_b in open_boxes:
    tmp_np = np.zeros(A)
    for one in one_b:
        tmp_np[all_boxes_dict[one]] += 1
        
    program_viewers_np.append(tmp_np)

target_reach = 1
    
upper_cost_limit = sum(all_cost)+1
result_reach = 0
result_cost = 0
result_indexes = set()
for i,one_programs in enumerate(program_viewers_np):
    # 各初期番組における結果格納用
    new_programs_np = one_programs[:]
    new_cost = all_cost[i]
    added_set = set([i])
    max_index = 0
    reach_num = len(new_programs_np[new_programs_np >= target_reach])

    while max_index != -1:
        # スコア作成
        max_score = 0
        max_index = -1
        for j,loop_program in enumerate(program_viewers_np):

            if j not in added_set and new_cost + all_cost[j] <= upper_cost_limit:
                tmp_programs_np = new_programs_np[:] + loop_program[:]
                tmp_score = (len(tmp_programs_np[tmp_programs_np >= target_reach])-reach_num)/all_cost[j]
                if tmp_score > max_score:
                    max_score = tmp_score
                    max_index = j

        if max_index != -1:
            new_programs_np = new_programs_np + program_viewers_np[max_index]
            new_cost += all_cost[max_index]
            added_set.add(max_index)


        # ユニークリーチが0のものがあればremove
        reach_num = len(new_programs_np[new_programs_np >= target_reach])
        remove_set = set()
        for added_index in added_set:
            tmp_programs_np = new_programs_np[:] - program_viewers_np[added_index][:]
            if len(tmp_programs_np[tmp_programs_np >= target_reach]) == reach_num:
                new_programs_np = new_programs_np -  program_viewers_np[added_index][:]
                new_cost -= all_cost[added_index]
                remove_set.add(added_index)

        added_set = set([one for one in added_set if not one in remove_set])

    if result_reach < reach_num:
        result_reach = reach_num
        result_cost = new_cost
        result_indexes = added_set

if result_reach == A:
    print(result_cost)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
data = []
opened = [False]*(N+1)

ans = 0
for _ in range(M):
  a,b = IL()
  c = IL()
  data.append([a, c])

data.sort()
#print(data)

for i in data:
  value, opennum = i
  f = 0
  for num in opennum:
    if opened[num] == False:
      opened[num] = True
      f = 1
  else:
    if f == 1:
      ans += value

for i in range(1,N+1):
  if opened[i] == False:
    print(-1)
    exit()
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
takara = [0] * n

for i in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	for j in range(b):
		ma = takara[c[j]-1]
		if ma == 0:
			takara[c[j]-1] = a
		else:
			takara[c[j]-1] = min(a, ma)

if 0 in takara:
	print("-1")
else:
	print(sum(set(takara)))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
B = []
C = []
for i in range(M):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)
  c = list(map(int,input().split()))
  C.append(c)
#print(A)
#print(B)
#print(C)

dp = [[0 for _ in range(N)] for _ in range(M+1)]
for i in range(M):
  for j in range(N):
    #print(i,j,dp[i][j])
    dp[i+1][j] = dp[i][j]
    if (j+1) in C[i] and (dp[i][j] == 0 or A[dp[i][j]-1] > A[i]):
      dp[i+1][j] = i+1
#print(dp)
key = set()
for k in dp[M]:
  if k == 0:
    print(-1)
    exit()
  key.add(k)
ans = 0
for k in key:
  ans += A[k-1]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
Key = []
for i in range(M):
    Key.append([int(k) for k in input().split()])
    Key[-1].append([int(c) for c in input().split()])
    
Key.sort(reverse=True)
ans = 0
K = [0 for i in range(N)]
for i in range(M):
    ans += Key[i][0]
    for j in range(N):
        if (j+1) in Key[i][2]:
            K[j] += 1

if 0 in K:
    print(-1)
else:
    for i in range(M):
        for j in range(Key[i][1]):
            K[Key[i][2][j]-1] -= 1
        if 0 in K:
            for j in range(Key[i][1]):
                K[Key[i][2][j]-1] += 1
        else:
            ans -= Key[i][0]
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(s) for s in input().split()]
key_lst=[]
for i in range(m):
  a,b=[int(s) for s in input().split()]
  op=[int(s) for s in input().split()]
  key_lst.append([a,op])
key_lst.sort()
#print(key_ls)
door2=[1 for _ in range(n)]
cost_ls=[]
#####最初に何かの鍵を買う
for i in range(m):
  key_ls=[e for e in key_lst]
  door=[0 for _ in range(n)]
  cost=0
  key=key_ls.pop(i)
  cost+=key[0]
  for x in key[1]:
    door[x-1]=1
  #####その後一番安い鍵から順にかっていく
  while True:
    if door==door2 : break
    if key_ls==[]:
      cost=-1
      break
    key=key_ls.pop(0)
    flag=0
    #まだ開いていない箱を開けられるか？
    for x in key[1]:
      if door[x-1]==0:
        flag=1
        break
    #開けられるなら購入
    if flag==1:
      cost+=key[0]
    for x in key[1]:
      door[x-1]=1
  cost_ls.append(cost)
  if cost==-1: break
print(min(cost_ls))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ans=[-1]*N
for i in range(M):
  x,y=map(int,input().split())
  l=list(map(int,input().split()))
  for j in l:
    if (ans[j-1]<0) or (ans[j-1]>x):
      ans[j-1] = x
l1=[n for n in ans if n<0]
res=0
ans2=[]
for k in ans:
  if k not in ans2:
    res+=k
    ans2.append(k)
print(-1 if len(l1)>0 else res)

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
    for k in kouho[i]:
        m = min(cost[k], m)
    if m not in used:
        ans += m
        used.append(m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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


price = [float("inf")]*n
using_key=[-1]*n

for i in range(m):
    now_price=0
    for g in c[i]:
        now_price+=price[g-1]
    if now_price>=ab[i][0]:
        for g in c[i]:
            price[g-1]=ab[i][0]
            using_key[g-1]=i
    

ans=sum(price)
if ans==float("inf"):
    print(-1)
    sys.exit()

ans=0
for i in set(using_key):
    ans+=ab[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
INF = 10**13
t2a = defaultdict(lambda : INF)
t2k = {}
N, M = map(int, input().split())
k2a = [0] * M
for m in range(M):
    a, b = map(int, input().split())
    k2a[m] = a
    C = tuple(map(int, input().split()))
    for ci in C:
        t2a[ci] = min(t2a[ci], a)
        if t2a[ci] == a:
            t2k[ci] = m

if len(t2a) != N:
    print(-1)
else:
    ans = 0
    for k in set(t2k.values()):
        ans += k2a[k]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
prices = [-1]*M
for i in range(M):
  A,B = map(int,input().split())
  prices[i] = A
  for c in map(int,input().split()): graph[c-1].append(i)

queue = deque()
queue.append([0,-1,0])
ans = float('inf')
flag = False
while len(queue) != 0:
  prv_box, prv_key, prv_prc = queue.pop()
  if prv_box == N:
    ans=min(ans,prv_prc)
    flag = True
    continue
  if prv_prc >= ans: continue
  if prv_key in graph[prv_box]:
    queue.append([prv_box+1, prv_key, prv_prc])
  else:
    for key in graph[prv_box]:
      queue.append([prv_box+1, key, prv_prc+prices[key]])
print(-1 if flag is False else 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)):
    # print("Try", items[i], costs[i])
    if (taken | items[i]) > taken:
        used.add(i)
        taken = taken | items[i]
        # print("Take")
    diff = costs[i]
    diffk = set()
    for j in used:
        if i != j and items[i] | items[j] == items[i]:
            diffk.add(j)
            diff -= costs[j]
    if diff < 0:
        # print("More efficient to take and drop", diffk)
        used = used - diffk

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

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_

n,m = get_nums_l()

keys = [999999999999999999999999] * (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

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 != 999999999999999999999999 else -1)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
ab = []
C = []
for _ in range(m):
    x = LI()
    ab.append(x)
    y = LI()
    C.append(y)

lst = [[] for _ in range(n)]
cnt = [0]*n
for i in range(m):
    a,b = ab[i]
    for j in C[i]:
        lst[j-1].append((a,i))
        cnt[j-1] += 1

for i in lst:
    i.sort()

for i in range(n):
    if len(lst[i]) == 0:
        print(-1)
        quit()

inde = cnt.index(min(cnt))
ans = inf
for i,j in lst[inde]:
    check = [1]*n
    tmp = i
    for k in C[j]:
        check[k-1] = 0
    while sum(check) != 0:
        for k in range(n):
            if check[k] != 0:
                tmp += lst[k][0][0]
                for l in C[lst[k][0][1]]:
                    check[l-1] = 0
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

# N = int(input())
# A = list(map(int, input().split()))
N, M = map(int, input().split())

# match = [[False] * N for _ in range(M)]
dest = []
cost = [0] * M


for i in range(M):
    cost[i] = int(input().split()[0])
    dest.append(sum([2 ** (n-1) for n in map(int, input().split())]))

# print(dest)

state = defaultdict(lambda: float('inf'))
state[0] = 0

for _ in range(N):
    for j in range(128):
        for k in range(M):
            state[j | dest[k]] = min(state[j | dest[k]], state[j]+cost[k])

ans = state[sum([2 ** (n-1) for n in range(1, N+1)])]

print(ans if ans < float('inf') else -1)

Submission status: Wrong Answer

Solution code:
import heapq as hq
inf = 10 ** 18

N, M = map(int, input().split())
n = 1 << N
dis = [inf] * n
que = []
key = []

for _ in range(M):
    a, _ = map(int, input().split())
    c = map(int, input().split())
    k = 0
    for x in c:
        k += 1 << (x-1)
    key.append((k, a))

dis[0] = 0
hq.heappush(que, (0, 0))

while que != []:
    # print(*dis)
    # print(que)
    d, v = hq.heappop(que)
    if d == dis[v]:
        for gain, cost in key:
            if not (gain & v) == gain:
                to = gain | v
                if dis[to] > d + cost:
                    dis[to] = d + cost
                    hq.heappush(que, (dis[to], to))
print(dis[n-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())))
x=[-1]*n
for _ in range(m):
  for i in range(m):
    f=False
    y=x[:]
    for j in k[i]:
      if y[j-1]==-1:f=True
      y[j-1]=i
    if f:x=y[:];continue

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

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
c=[]
a=[]
l=[[] for i in range(n+1)]
dp=[10**18]*(2**(n))
for i in range(m):
    x,y=[int(j) for j in input().split()]
    a.append(x)
    tmp=set([int(j) for j in input().split()])
    c.append(tmp)
    ind=0
    for i in range(1,n+1):
        if i in tmp:
            ind+=2**(i-1)
    dp[ind]=x

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:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0] * M
keys = [0] * M
inf = 10 ** 12
for i in range(M):
    a[i], _ = map(int, input().split())
    c_list = list(map(int, input().split()))
    keys[i] = sum([2 ** j for j in range(N) if j + 1 in c_list])

dp = [inf] * (2 ** N)
dp[0] = 0

# print(keys)

for i in range(M):  # use key i
    for j in range(N ** 2):
        # print(dp, j, keys[i], dp[j | keys[i]], dp[j], a[i])
        dp[j | keys[i]] = min(dp[j] + a[i], dp[j | keys[i]])

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

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_dict
kpd = 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]:
        kpd[key].append(am)

def solve():
    ans = 0
    # print(kpd)
    prev_plus = []
    for i in range(1, N + 1):
        if len(kpd[i]) == 0:
            ans = -1
            break
        price = min(kpd[i])
        if price in prev_plus:
            continue
        ans += price
        prev_plus.append(price)
    return ans

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
dp = [[10**10 for i in range(m+1)] for j in range(1<<n)]

for i in range(m+1):
    dp[(1<<n)-1][i] = 0
#print(dp)

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    S_c = 0
    for x in c:
        S_c += 1<<(x-1)
    #print(S_c)
    for s in range(1<<n):
        if s == 2 and i == 0:
            print(a + dp[s | S_c][i])
        dp[s][i+1] = min(dp[s][i],a+dp[s | S_c][i],dp[s][i+1])

    #print(dp)

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    for i in range(b):
        l[c[i]-1].append([a,b,c])
box = [0 for i in range(n)]
ans = 0
key = 0
for i in range(n):
    if box[i] == 0:
        if len(l[i]) == 0:
            key = 1
            break
        else:
            l[i].sort(key=lambda x:x[0])
            a1,b1,c1 = l[i][0]
            for j in range(b1):
                box[c1[j]-1] += 1
            ans += a1
if key == 0:
    print(ans)
else:
    print(-1)