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
from collections import Counter
input=sys.stdin.readline
ans=0
n,m=map(int,input().split())
l=[]
kagi=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    l+=c
    ans+=a
    c.insert(0,a)
    kagi.append(c)
cou=Counter(l)
if len(cou)!=n:
    print(-1)
    exit()
kagi.sort(key=lambda x:x[0],reverse=True)
ansl=[ans]
for i in range(m):
    f=1
    for x in kagi[i][1:]:
        if cou[x]==1:
            f=0
        else:
            cou[x]-=1
    if f:
        ans-=kagi[i][0]
ansl.append(ans)
for j in range(m):
    ans=ansl[0]
    for i in range(m-1):
        if i==j:
            continue
        f=1
        for x in kagi[i][1:]:
            if cou[x]==1:
                f=0
            else:
                cou[x]-=1
        if f:
            ans-=kagi[i][0]
    ansl.append(ans)
print(min(ansl))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np


# noinspection PyShadowingBuiltinsInspection

def main():
    n, m = [int(x) for x in input().split()]
    key_cost = []
    key_class = []
    key_n = []
    cheapest_keys = [-1] * n
    for i in range(m):
        a, b = [int(x) for x in input().split()]
        key_cost.append(a)
        key_n.append(b)
        key_class.append(set([int(x) for x in input().split()]))
        for j in range(1, n+1):
            if j in key_class[-1]:
                if cheapest_keys[j - 1] == -1:
                    cheapest_keys[j - 1] = i
                elif key_cost[cheapest_keys[j - 1]] > key_cost[-1]:
                    cheapest_keys[j - 1] = i
    if -1 in cheapest_keys:
        print(-1)
        return
    key_n = np.array(key_n)
    
    for i in np.argsort(-key_n):
        kouho = set()
        for j in key_class[i]:
            if cheapest_keys[j - 1] != i:
                kouho.add(cheapest_keys[j - 1])
        sum = 0
        for j in kouho:
            sum += key_cost[j]
        if key_cost[i] <= sum:
            for j in key_class[i]:
                cheapest_keys[j - 1] = i
    ret = 0
    for i in set(cheapest_keys):
        ret += key_cost[i]
    print(ret)
    return


if __name__ == "__main__":
    main()

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 = dp[m % 2][-1]
if ans == int(2e8):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    can_open = dict()
    key_count = dict()
    for i in range(N): 
        key_count[i] = 0

    q = []
    heapq.heapify(q)

    cost = 0
    for i in range(M):
        a, b = map(int, input().split())
        cost += a
        key  = [int(k) - 1 for k in input().split()]
        qk = [-a, b]
        for k in key: 
            qk.append(k)
            key_count[k] += 1
        heapq.heappush(q, qk)

    for c in key_count:
        if key_count[c] == 0:
            print(-1)
            break
    else:
        while q:
            now_key = heapq.heappop(q)
            can_delete = False
            for k in now_key[2:]:
                if key_count[k] == 1: break
            else:
                cost += now_key[0]
                for k in now_key[2:]: key_count[k] -= 1

        print(cost)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
def get_dp(x):
    return sum([2**i for i in x])
a = []
c = []
d=set()
for j in range(m):
    a2, _ = [int(i) for i in input().split()]
    a.append(a2)
    temp=[int(i)-1 for i in input().split()]
    c.append(get_dp(temp))
    d |= set(temp)

if len(d) != n:
    print(-1)
    exit()


dp = [10**10] * (2 ** n)
dp[0] = 0
for i,m in zip(c,a):
    for j, k in enumerate(dp):
        if k != 10**10:
            print(i)
            l=j|i
            dp[l] = min(dp[l], k + m)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
v = []
key = []
ans = [10**9] * n
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in c:
        ans[j - 1] = min(ans[j - 1], a)

for i in ans:
    if i == 10 ** 9:
        print(-1)
        exit()
print(sum(set(ans)))

Submission status: Wrong Answer

Solution code:
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])
    C.append(c)

# print(ab, C)
ab.sort()
# print(ab)

cost = 0
bag = [False] * (n+1)
for i in range(m):
    for j in ab[i][2]:
        if bag[j] == False:
            bag[j] = True
            cost += ab[i][0]
    tmp = [False] * (n+1)
    for j in ab[i][2]:
        tmp[j] = True
        if bag == tmp:
            if cost > ab[i][0]:
                cost = ab[i][0]
                bag = tmp

cnt = 0
for i in range(n+1):
    if bag[i] == True:
        cnt += 1

if cnt == n:
    print(cost)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n,m=[int(s) for s in input().split()]
key_ls=[]
for i in range(m):
  a,b=[int(s) for s in input().split()]
  op=[int(s) for s in input().split()]
  key_ls.append([a,op])
key_ls.sort()
#print(key_ls)
door=[0 for _ in range(n)]
door2=[1 for _ in range(n)]
cost=0
#####一番安い鍵から順にかっていく
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
    
print(cost)

Submission status: Wrong Answer

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

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

ans = [-1] * N
A = [-1] * M

for m in range(M):
    A[m], B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    for c in C:
        if A[ans[c-1]] == -1 or A[ans[c-1]] > A[m]:
            ans[c-1] = m

if ans.count(-1) > 0:
    print(-1)
    sys.exit(0)

total = 0
for i in set(ans):
    total += A[i]
print(total)

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  C=[int(i) for i in input().split()]
  x=0
  for c in C:
    x|=(1<<(c-1))
  A.append((a,x))
DP=[float("inf")]*(2**n)
DP[0]=0
for i in range(m):
  a,x=A[i]
  for j in range(2**n):
    if (j&x)==j:
      DP[j]=min(DP[j],a)

    DP[j]=min(DP[j],DP[j^x]+a)

print(-1 if DP[2**n-1]==float("inf") else DP[2**n-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np


# noinspection PyShadowingBuiltinsInspection

def main():
    n, m = [int(x) for x in input().split()]
    key_cost = []
    key_class = []
    cheapest_keys = [-1] * n
    for i in range(m):
        a, b = [int(x) for x in input().split()]
        key_cost.append(a)
        key_class.append(set([int(x) for x in input().split()]))
        for j in range(1, n+1):
            if j in key_class[-1]:
                if cheapest_keys[j - 1] == -1:
                    cheapest_keys[j - 1] = i
                elif key_cost[cheapest_keys[j - 1]] > key_cost[-1]:
                    cheapest_keys[j - 1] = i
    if -1 in cheapest_keys:
        print(-1)
        return
    for i in range(m):
        kouho = set()
        for j in key_class[i]:
            if cheapest_keys[j - 1] != i:
                kouho.add(cheapest_keys[j - 1])
        sum = 0
        for j in kouho:
            sum += key_cost[j]
        if key_cost[i] <= sum:
            for j in key_class[i]:
                cheapest_keys[j - 1] = i
    ret = 0
    for i in set(cheapest_keys):
        ret += key_cost[i]
    print(ret)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

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

def one_str():
    return input()

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

N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    treasures.append(many_int())

import copy

goal_set=set([i+1 for i in range(N)])
def dfs(now_moneys, index, now_open):
    if len(goal_set&now_open) == len(goal_set):
        return now_moneys
    
    if index < N:
        no_use = dfs(copy.deepcopy(now_moneys), index+1, copy.deepcopy(now_open))
        try:
            now_moneys+=key_list[index]
        except:
            now_moneys=-1
            return now_moneys
        now_open =now_open | set(treasures[index])
        use = dfs(copy.deepcopy(now_moneys), index+1, copy.deepcopy(now_open))
        return min(use,no_use)
    return 10**15

temp=dfs(now_moneys=0, index=0, now_open=set([]))

if temp == 10**15:
    print(-1)
else:
    print(temp)

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 + 1) % 2][j | k], dp[i % 2][j] + a)
ans = dp[m % 2][-1]
if ans == int(2e8):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

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

q = [list() for _ in range(N)]
for k in range(M):
    a, b = map(int, input().split())
    for c in map(int, input().split()):
        heappush(q[c - 1], (a, k))

q.sort(key=lambda x: len(x))

cost = 0
seen = set()
for queue in q:
    if len(queue) == 0:
        print(-1)
        exit(0)
    a, k = heappop(queue)
    if k in seen:
        continue
    else:
        cost += a
        seen.add(k)
print(cost)

Submission status: Wrong Answer

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

h = []
for i in range(M):
    a, b = list(map(int, readline().split()))
    c = list(map(int, readline().split()))
    bi = ['0'] * N
    for cc in c:
        bi[cc-1] = '1'
    h.append([a,b,int(''.join(bi), 2)])

h.sort(key=lambda x: x[0])
# print(h)

p = h[0][0]
bit = h[0][2]
for i in range(M-1):
    tmp = bit
    res = bit | h[i+1][2]
    # print(tmp,res)
    if tmp != res:
        bit = res
        p += h[i+1][0]

if bin(bit) == '0b' + '1' * N:
    print(p)
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

dp = [[] for j in range(n)]

keys = []
for i in range(m):
    a, b = nm()
    c = nl()

    keys.append([ci -1 for ci in c])
    for j in range(b):
        dp[c[j] - 1].append((a, i))

for d in dp:
    d.sort()


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

got_keys = set()
pos = [0] * n

ans = 0

while (True):
    min_cost = 10 ** 6
    mc_ind = -1

    if len(got_keys) == n:
        break
    for i in range(n):
        if i in got_keys:
            continue
        c = dp[i][pos[i]][0]
        key = dp[i][pos[i]][1]
        if min(c, min_cost) == c:
            min_cost = c
            mc_ind = i
        got_keys |= set(keys[key])
        ans += c

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    d = defaultdict(list)
    for i in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        for c in C:
            if d[c]:
                if d[c][0] > a:
                    d.pop(c)
                    d[c].append(a)
                    d[c].append(i)
            else:
                d[c].append(a)
                d[c].append(i)

    ans = 0
    cnt = 0
    use_list = set()
    for i,j in d.items():
        if j[1] in use_list:
            cnt += 1
            continue
        else:
            ans += j[0]
            cnt += 1
            use_list.add(j[1])

    if cnt == N:
        print(ans)
    else:
        print(-1)


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input=sys.stdin.readline
ans=0
n,m=map(int,input().split())
l=[]
kagi=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    l+=c
    ans+=a
    c.insert(0,a)
    kagi.append(c)
cou=Counter(l)
if len(cou)!=n:
    print(-1)
    exit()
kagi.sort(key=lambda x:x[0],reverse=True)
for i in range(m):
    f=1
    for x in kagi[i][1:]:
        if cou[x]==1:
            f=0
        else:
            cou[x]-=1
    if f:
        ans-=kagi[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    key_set = set(map(int, input().split()))
    key_bin = 0
    for c in key_set:
        key_bin += (2**(c-1))
    keys.append([a, key_bin])


N_bin = 2**(N)
# i番目までのkeyで
dp = [[float('inf')]*N_bin for _ in range(2)]
dp[0][0] = 0
for key in range(M):  # 新加えるkey
    key_val, key_set = keys[key]
    for bit in range(N_bin):  # 加える前の状態
        dp[(key+1) % 2][bit | key_set] = min(dp[(key+1) % 2]
                                             [bit | key_set], dp[(key % 2)][bit | key_set], dp[key % 2][bit]+key_val)
ans = float('inf')
for c in range(2):
    ans = min(ans, dp[c][-1])
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [float("inf")]*(2**n)
for _ in range(m):
    a,b = map(int,input().split())
    c = tuple(map(int,input().split()))
    jkl = 0
    for e in c:
        jkl += 1 << (e-1)
    dp[jkl] = min(dp[jkl],a)

tank = []
new = [0]
used = [True]*(2**n)

while len(new) != 0:
    tank = []
    for e in new:
        p = []
        q = []
        for i in range(n):
            if (e>>i)&1 == 0:
                p.append(i)
            else:
                q.append(i)

        for ep in p:
            if used[e+(1<<ep)]:
                tank.append(e+(1<<ep))
                used[e+(1<<ep)] = False

        if len(q) <= 1:
            continue
        for i in range(len(q)-1):
            for j in range(i+1,len(q)):
                dp[e] = min(dp[e],dp[e-(1<<q[i])]+dp[e-(1<<q[j])])

    new = tank

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

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict
INF = 10**13
t2a = defaultdict(lambda : INF)
N, M = map(int, input().split())
keys = set()
for m in range(M):
    a, b = map(int, input().split())
    C = tuple(map(int, input().split()))
    t2a[C] = min(t2a[C], a)
    keys.add(C)
keys = list(keys)
for i in range(1, N+1):
    ts = filter(lambda x: len(x) <= i, keys)
    for x1, x2 in itertools.combinations(ts, 2):
        x12 = tuple(sorted(set(x1)|set(x2)))
        t2a[x12] = min(t2a[x1] + t2a[x2], t2a[x12])
ans_key = tuple(range(1, N+1))
# print(t2a)
if t2a[ans_key] == INF:
    print(-1)
else:
    print(t2a[ans_key])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
box = [[-1, 0] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    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:
def two_int():
    N, K = map(int, input().split())
    return N,K

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

def one_str():
    return input()

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

N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    treasures.append(many_int())

import copy

goal_set=set([i+1 for i in range(N)])
def dfs(now_moneys, index, now_open):
    if len(goal_set&now_open) == len(goal_set):
        return now_moneys
    
    if index < N:
        no_use = dfs(copy.deepcopy(now_moneys), index+1, copy.deepcopy(now_open))
        try:
            now_moneys+=key_list[index]
        except:
            now_moneys=-1
            return now_moneys
        now_open =now_open | set(treasures[index])
        use = dfs(copy.deepcopy(now_moneys), index+1, copy.deepcopy(now_open))
        return min(use,no_use)
    return 10**15

print(dfs(now_moneys=0, index=0, now_open=set([])))

Submission status: Wrong Answer

Solution code:
#E問題
N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    ABC.append([a,b,c])
    
keys = [[] for i in range(N)]
for i in range(M):
    a,b,c = ABC[i]
    for cs in c:
        keys[cs-1].append(i)

        
inf = float("inf")
MIN = inf

if [] in keys:
    print(-1)
else:
    used = [0 for i in range(N)]
    cost = 0
    for abc in ABC:
        a,b,c = abc
        for cs in c:
            used[cs-1]+=1
        cost+=a
        
    ABC.sort(reverse=True)
    for abc in ABC:
        a,b,c = abc
        flag = 0
        for cs in c:
            if used[cs-1] == 1:
                flag = 1
                break
            else:
                used[cs-1]-=1
        if flag == 0:
            cost-=a
            
    print(cost)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
inf=10**12

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

class MinCostFlow:
    def __init__(self,n):
        self.n=n
        self.edges=[[] for i in range(n)]
    def add_edge(self,fr,to,cap,cost):
        self.edges[fr].append([to,cap,cost,len(self.edges[to])])
        self.edges[to].append([fr,0,-cost,len(self.edges[fr])-1])
    def MinCost(self,source,sink,flow):
        n=self.n; E=self.edges
        prev_v=[0]*n; prev_e=[0]*n
        s=set()
        while flow:
            dist=[inf]*n
            dist[source]=0
            q=deque([source])
            Flag=[False]*n
            Flag[source]=True
            while q:
                v=q.popleft()
                if not Flag[v]:
                    continue
                Flag[v]=False
                #min_dist flow
                for i,(to,cap,cost,_) in enumerate(E[v]):
                    if cap>0 and dist[to]>dist[v]+cost:
                        dist[to]=dist[v]+cost
                        prev_v[to],prev_e[to]=v,i
                        q.append(to)
                        Flag[to]=True
            #print(dist)
            f,v=flow,sink
            while v!=source:
                #min_flow go to sink
                f=min(f,E[prev_v[v]][prev_e[v]][1])
                v=prev_v[v]
            if f==0:
                return -1
            flow-=f
            s.add(dist[sink])
            #print(mincost,s)
            v=sink
            #update flow
            while v!=source:
                E[prev_v[v]][prev_e[v]][1]-=f
                rev=E[prev_v[v]][prev_e[v]][3]
                E[v][rev][1]+=f
                v=prev_v[v]
        return sum(s)
flow=MinCostFlow(n+m+2)
s=n
for i in range(m):
    flow.add_edge(0,i+1,ab[i][1],ab[i][0])
    for c in cs[i]:
        flow.add_edge(i+1,m+c,1,0)
for i in range(n):
    flow.add_edge(m+i+1,m+n+1,1,0)
print(flow.MinCost(0,m+n+1,s))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def solve():
  n,m = (int(i) for i in input().split())
  c = []
  buy = [False]*n
  for i in range(m):
    a,b = (int(i) for i in input().split())
    tmp = list(int(i) for i in input().split())
    c.append(((a/b,a),tmp))
  c.sort()
  c = deque(c)
  tc = deque(c)
  ans = 0
  while c:
    info,key = c.popleft()
    scrap,value = info
    for i in range(len(key)):
      buy[key[i]-1] = True
    ans += value
    #更新
    newc = []
    for i in range(len(c)):
      gomib,key = c[i]
      gomib,a = gomib
      newb = 0
      for i in range(len(key)):
        tmp = key[i]-1
        if not buy[tmp]:
          newb += 1
      if newb != 0:
        newc.append(((a/newb,a),key))
    newc.sort()
    c = deque(newc)
  judge = 1
  for i in range(n):
    if not buy[i]:
      print("-1")
      exit()
  
  for i in range(m):
   buy = [False]*n
   c = tc
   for i in range(m):
    if len(c) >0:
      c.popleft()
   nans = 0
   while c:
    info,key = c.popleft()
    scrap,value = info
    for i in range(len(key)):
      buy[key[i]-1] = True
    nans += value
    #更新
    newc = []
    for i in range(len(c)):
      gomib,key = c[i]
      gomib,a = gomib
      newb = 0
      for i in range(len(key)):
        tmp = key[i]-1
        if not buy[tmp]:
          newb += 1
      if newb != 0:
        newc.append(((a/newb,a),key))
    newc.sort()
    c = deque(newc)
   judge = 1
   for i in range(n):
    if not buy[i]:
      judge = -1
      break
   if judge== 1:
     ans = min(ans,nans)
  
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
print('haha')

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]

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

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

taken = 0
used = set()
cost = 0
for i in range(len(keys)):
    if taken | items[i] > taken:
        cost += costs[i]
        used.add(i)
        taken = taken | items[i]
    else:
        diff = costs[i]
        diffk = set()
        for j in used:
            if items[i] | items[j] == items[i]:
                diffk.add(j)
                diff -= costs[j]
        if diff < 0:
            used = used - diffk
            cost = cost + diff

if taken == int(2 ** n - 1):
    print(cost)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n,m=[int(i) for i in input().split()]
keys_v=[[] for _ in range(n)]
openable=[]

s=0

for i in range(m):
    a,_=[int(i) for i in input().split()]
    c=[int(i) for i in input().split()]
    openable.append(c)
    for j in c:
        keys_v[j-1].append((i,a))

locked=[1]*n

for i,v in enumerate(locked):
    if v:
        try:
            b=min(keys_v[i],key=lambda x:x[1])
        except:
            print(-1)
            exit()
        s+=b[1]
        for k in openable[b[0]]:
            locked[k-1]=0

print(s)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = []
ls2 = []
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    ls.append([a,b])
    ls2.append(c)
    
nls = []
for i in range(1,n+1):
    nls.append(i)
    
al = []
    
for i in range(len(ls2)):
    for j in range(i+1,len(ls2)):
        ans = []
        ans = ls2[i] + ls2[j]
        ans = sorted(set(ans))
        if ans == nls:
            al.append(ls[i][0]+ls[j][0])
            
if al == []:
    print(-1)
else:
    print(min(al))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
NL = [0 for i in range(N)]
ABC = []
ans = 0
for i in range(M):
    ai,bi = map(int,input().split())
    ci = list(map(int,input().split()))
    for j in range(len(ci)):
        ci[j] -= 1
        NL[ci[j]] += 1
    ans += ai
    ABC.append([ai,bi,ci])
if 0 in NL:
    print(-1)
else:
    
    ABC.sort(key=lambda x: x[0],reverse=True)
    ABC.sort(key=lambda x: x[1])
    for i in range(M):
        use = False
        for j in range(len(ABC[i][2])):
            if NL[ABC[i][2][j]] == 1:
                use = True
                break
        if use:
            pass
        else:
            ans -= ABC[i][0]
            for j in range(len(ABC[i][2])):
                NL[ABC[i][2][j]] -= 1

    print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
  N, M = map(int, input().split())
  keys = [0] * N
  products = []
  costs = 0

  for i in range(M):
    A, B = map(int, input().split())
    costs += A
    key = [int(i) - 1 for i in input().split()]
    for k in key:
      keys[k] += 1
    products.append((A, key))

  products.sort(key=lambda product: product[0], reverse=True)

  for k in keys:
    if k < 1: return -1

  for cost, key in products:
    isNeed = False
    for k in key:
      if keys[k] == 1:
        isNeed = True
        break
    if isNeed: continue
    for k in key:
      keys[k] -= 1
    costs -= cost

  return costs

print(solve())

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]

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

costs, items = zip(*keys)

taken = 0
used = set()
cost = 0
for i in range(len(keys)):
    if taken | items[i] > taken:
        cost += costs[i]
        used.add(i)
        taken = taken | items[i]
    else:
        diff = costs[i]
        diffk = set()
        for j in used:
            if items[i] | items[j] == items[i]:
                diffk.add(j)
                diff -= costs[j]
        if diff < 0:
            used = used - diffk
            cost = cost + diff

if taken == int(2 ** n - 1):
    print(cost)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
t=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    t.append([a,c])
t=sorted(t)
d=0
c=[-1]*n
for i in range(m):
    for j in t[i][1]:
        if c[j-1]==-1:
            for h in t[i][1]:
                c[h-1]=i
            break
    if -1 not in c:
        print(sum(t[i][0]for i in set(c)))
        break
else:
    print(-1)

Submission status: Wrong Answer

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

AB = []
AB_append = AB.append
C = []
C_append = C.append
for _ in range(M):
    a, b = map(int, input().split())
    AB_append((a, b))
    c = list(map(int, input().split()))
    C_append(c)


ans = 10 ** 18
for i in range(2 ** N):
    s = set()
    tmp = 0
    flag = False
    for j in range(M):
        if flag:
            break
        if (i >> j) & 1: #j桁目が1の時
            #-------------------------------------------
            #
            for c in C[j]:
                s.add(c)
            tmp += AB[j][0]
            if len(s) == N:
                ans = min(ans,tmp)
                flag = True
            if tmp >= ans:
                flag = True
            #-------------------------------------------

if ans == 10 ** 18:
    print (-1)
    exit()
print (ans)

Submission status: Wrong Answer

Solution code:
print([]*3)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
box = [[-1, 0] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    count = 0
    hikaku_key = set()
    for j in c:
        j -= 1
        if box[j][0] == -1:
            box[j][0] = i
            box[j][1] = a
        elif box[j][0] not in hikaku_key:
            count += box[j][1]
            hikaku_key.add(box[j][0])
    if a < count:
        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:
from heapq import heappop, heappush

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

q = [list() for _ in range(N + 1)]
for k in range(M):
    a, b = map(int, input().split())
    for c in map(int, input().split()):
        heappush(q[c], (a, k))

cost = 0
seen = set()
for queue in q[1:]:
    if len(queue) == 0:
        print(-1)
        exit(0)
    a, k = heappop(queue)
    if k in seen:
        continue
    else:
        cost += a
        seen.add(k)
print(cost)