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:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    go = g
    myset = set([1])
    sq = int(sqrt(g)) + 2

    for i in range(2, sq):
        while g % i == 0:
            g /= i
            myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            myset.add(go)

    print(len(myset))

    return

# E


def E():
    N, M = LI()

    price = [-1] * N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a or price[k-1] == -1:
                price[k-1] = a
    if -1 in price:
        print(-1)
    else:
        print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    go = g
    myset = set([1])
    sq = int(sqrt(g)) + 2

    for i in range(2, sq):
        while g % i == 0:
            g /= i
            myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            myset.add(go)

    print(len(myset))

    return

# E


def E():
    N, M = LI()

    price = [-1] * N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a or price[k-1] == -1:
                price[k-1] = a
    print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def main():
    N, M = map(int,input().split())
    maxval = 10 ** (5 + 3 + 2)
    dp = [maxval] * (2 ** N)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        clist = list(map(int,input().split()))
        for ci in clist:
            c |= 1 << (ci - 1)

        newopen = set()
        for op in opened:
            check = op | c
            dp[check] = min(dp[op] + a, dp[check])
            #print(check,len(dp),dp[check])
            newopen.add(c)

        opened = opened | newopen
        
    ans = dp[-1]
    if ans == maxval:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[[0]*2**n for _ in range(m)]
a,b=map(int,input().split())
C=list(map(int,input().split()))
C_num=sum(2**(c-1) for c in C)
for i in range(1,2**n):
    if (C_num-i)^i==C_num:
        dp[0][i]=a
    else:
        dp[0][i]=float("inf")
for k in range(1,m):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    C_num=sum(2**(c-1) for c in C)
    for i in range(1,2**n):
        dp[k][i]=min(dp[k-1][i],dp[k-1][i-C_num&i]+a)
if dp[-1][-1]==float("inf"):
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[[0]*2**n for _ in range(m)]
a,b=map(int,input().split())
C=list(map(int,input().split()))
C_num=sum(2**(c-1) for c in C)
for i in range(1,2**n):
    if (C_num-i)^i==C_num:
        dp[0][i]=a
    else:
        dp[0][i]=float("inf")
for k in range(1,m):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    C_num=sum(2**(c-1) for c in C)
    for i in range(1,2**n):
        dp[k][i]=min(dp[k-1][i],dp[k-1][i-C_num&i]+a)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def main():
    N, M = map(int,input().split())
    Keys = []
    Call = 0
    Tall = 0
    for Ti in range(N):
        Tall |= 1 << (Ti + 1)
    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        for ci in map(int,input().split()):
            c |= 1 << ci
        Call |= c
        Keys.append((a,b,c))

    if Call != Tall:
        print(-1)
        return

    Keys.sort()
    Ans = 0
    for K in Keys:
        Tprv = Tall
        Tall &= ~K[2]
        if Tprv != Tall:
            Ans += K[0]
        if Tall == 0:
            break

    print(Ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce

n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if len(reduce(lambda x, y: list(set(x)|set(y)), c))<n:
    print(-1)
    sys.exit()


def f(k, boxnum, cost, canopen):
    #cost = cost
    tmpcost = 100000
    for keynum in range(k, m+1):
        if boxnum in c[keynum-1]:
            if a[keynum-1] < tmpcost:
                tmpcost = a[keynum-1]
                canopen = canopen|set(c[keynum-1])
    if tmpcost==100000:
        tmpcost=0
    return cost+tmpcost, canopen

mincost=sum(a)
for j in range(1, m+1):
    tmpmincost = mincost
    canopen = set(c[j-1])
    cost = a[j-1]
    for i in range(1, n+1):
        canopen = canopen|set(c[j-1])
        
        if i not in canopen:
            cost, canopen = f(j, i, cost, canopen)
            #print('key,box=', j, i, canopen, cost)
    if len(canopen)==n:
        tmpmincost = cost if cost<tmpmincost else tmpmincost
        #print(tmpmincost)
    mincost = tmpmincost if tmpmincost<mincost else mincost
print(mincost)

Submission status: Wrong Answer

Solution code:
import os

N, M = map(int, input().split())
a = []
b = []
c = []
for i in range(M):
    _a, _b = map(int, input().split())
    _c = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c.append(_c)

candi = [ (i, 10**9) for i in range(N)]
for i in range(M):
    cost = a[i]
    boxes = c[i]
    for box in boxes:
        if cost < candi[box-1][1]:
            candi[box-1] = (i, cost)

costs = [ca[1] for ca in candi]
if any([cost == 10**9 for cost in costs]):
    print(-1)
    os.sys.exit()

idx = set([ca[0] for ca in candi])
ans = 0
for id in idx:
    ans += a[id]
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc142/submissions/7753443

N,M = map(int,input().split())
 
lis = [float("inf")] * (2 ** N)
lis[0] = 0
 
for i in range(M):
 
    a,b = map(int,input().split())
 
    c = list(map(int,input().split()))
 
    num = 0
    for j in c:
        num += 2 ** (j-1)
 
    nlis = lis.copy()
    for j in range(2 ** N):
 
        if lis[j | num] > nlis[j] + a:
            lis[j | num] = nlis[j] + a     
 
#print (lis)
if lis[2 ** N -1] == float("inf"):
    print (-1)
 
else:
    print (lis[2 ** N - 1])
    print (lis)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m=MI()
t=1<<n
key=[]
for i in range(m):
    a,b=MI()
    c=0
    for j in LI_():
        c+=1<<j
    key.append((a,c))
inf=float('inf')
dp=[[inf]*(m+1) for _ in range(t)]
#dp[stat][m] # min value using up to m and open stat
dp[0][0]=0

for j in range(1,m+1):
    for i in range(t):
        cost,ck=key[j-1]
        show(i,j,'|',dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        dp[ck|i][j]=min(dp[ck|i][j],dp[ck|i][j-1],dp[i][j-1]+cost)
        dp[i][j]=min(dp[i][j],dp[i][j-1])
        
for i in dp:
    show(*i)

ans=dp[t-1][m] if dp[t-1][m]!='inf' else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split(' '))
k1 = [];k2=[]
for i in range(M):
  k1.append(list(map(int,input().split(' ')))[0])
  k2.append(list(map(int,input().split(' '))))
pos = []
for i in range(N):
  pos.append([])
  for j,lst in enumerate(k2):
    if i+1 in lst:
      pos[i].append(j)
ans = 0
ans1 = []
i = 0
while i < N:
  if i+1 in ans1:
    i += 1
    continue
  if len(pos[i]) == 0:
    print(-1)
    exit()
  elif len(pos[i]) == 1:
    num = pos[i][0]
    ans += k1[num]
    ans1.append(i+1)
    i += 1
  else:
    prices = []
    for j in pos[i]:
      prices.append(k1[j])
    mini = min(prices)
    num = prices.index(mini)
    ans += mini
    ans1.extend(k2[pos[i][num]])
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce

n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if len(reduce(lambda x, y: list(set(x)|set(y)), c))<n:
    print(-1)
    sys.exit()


def f(k, boxnum, cost, canopen):
    #cost = cost
    tmpcost = 100000
    for keynum in range(k, m):
        if boxnum in c[keynum-1]:
            if a[keynum-1]<=tmpcost:
                canopen = canopen|set(c[keynum-1])
                tmpcost = a[keynum-1]
    return cost+tmpcost, canopen

mincost=sum(a)
for k in range(1, m):
    cost=0
    canopen = set()
    for i in range(n): #box
        if i+1 not in canopen:
            cost, canopen = f(k, i+1, cost, canopen)
            #print(canopen, cost)
    if cost < mincost:
        mincost = cost
print(mincost)

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce

n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if len(reduce(lambda x, y: list(set(x)|set(y)), c))<n:
    print(-1)
    sys.exit()

mincost = sum(a)

def f(boxnum, cost, canopen):
    #cost = cost
    tmpcost = 100000
    for keynum in range(m):
        if boxnum in c[keynum]:
            if a[keynum]<=tmpcost:
                canopen = canopen|set(c[keynum])
                tmpcost = a[keynum]
            #elif a[keynum]=tmpcost:
            #   canopen = c[keynum]|set(c[keynum]) 
    return cost+tmpcost, canopen

cost=0
canopen = set()
for i in range(1, n+1): #box
    if i not in canopen:
        cost, canopen = f(i, cost, canopen)
    #print(i, canopen)
print(cost)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m=MI()
t=1<<n
key=[]
for i in range(m):
    a,b=MI()
    c=0
    for j in LI_():
        c+=1<<j
    key.append((a,c))
inf=float('inf')
dp=[[inf]*(m+1) for _ in range(t)]
#dp[stat][m] # min value using up to m and open stat
dp[0][0]=0

for j in range(1,m+1):
    for i in range(t):
        cost,ck=key[j-1]
        #show(dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        show(i,j,'|',dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        dp[ck|i][j]=min(dp[ck|i][j-1],dp[i][j-1]+cost,dp[ck|i][j])
        
        
        #show('i,j=',bin(i),j,'key=',bin(ck),cost,'ck|i',bin(ck|i),dp[ck|i][j-1],dp[i][j-1]+cost,dp[ck|i][j],dp[1][1])

for i in dp:
    show(*i)

ans=dp[t-1][m] if dp[t-1][m]!='inf' else -1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m=MI()
t=1<<n
key=[]
for i in range(m):
    a,b=MI()
    c=0
    for j in LI_():
        c+=1<<j
    key.append((a,c))

dp=[[10**18]*(m+1) for _ in range(t)]
#dp[stat][m] # min value using up to m and open stat
dp[0][0]=0

for j in range(1,m+1):
    for i in range(t):
        cost,ck=key[j-1]
        #show(dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        show(i,j,'|',dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        dp[ck|i][j]=min(dp[ck|i][j-1],dp[i][j-1]+cost,dp[ck|i][j])
        
        
        #show('i,j=',bin(i),j,'key=',bin(ck),cost,'ck|i',bin(ck|i),dp[ck|i][j-1],dp[i][j-1]+cost,dp[ck|i][j],dp[1][1])

for i in dp:
    show(*i)

print(dp[t-1][m])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

cost = 100000*m
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
if cost == 100000*m:
    print(-1)
else:
    print(cost)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m=MI()
t=1<<n
key=[]
for i in range(m):
    a,b=MI()
    c=0
    for j in LI_():
        c+=1<<j
    key.append((a,c))

dp=[[10**18]*(m+1) for _ in range(t)]
#dp[stat][m] # min value using up to m and open stat
dp[0][0]=0
    
for j in range(1,1+m):
    for i in range(t):
        ck=key[j-1][1]
        cost=key[j-1][0]
        show(dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        dp[ck|i][j]=min(dp[ck|i][j-1],dp[i][j-1]+cost,dp[ck|i][j])
        
        show('i,j=',bin(i),j,'key=',bin(ck),cost,'ck|i',bin(ck|i),dp[ck|i][j-1],dp[i][j-1]+cost,dp[ck|i][j],dp[1][1])


    
print(dp[t-1][m])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

cost = 100000*n
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
if cost == 100000*n:
    print(-1)
else:
    print(cost)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

cost = 100000*n
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
print(cost)

if cost == 100000*n:
    print(-1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

cost = 100000*n
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
if cost == 100000*n:
    print(-1)
            
print(cost)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

cost = 100000
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
if cost == 100000:
    print(-1)
            
print(cost)

Submission status: Wrong Answer

Solution code:
import sys

n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if n > max(b):
    print(-1)
    sys.exit()

cost = 100000
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
            
print(cost)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, b = [], []
c = []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)

if n > max(b):
    print(-1)

cost = 100000
for i in range(m):
    if len(c[i])==n:
        cost = a[i] if a[i]<cost else cost
    
    for j in range(i+1, m):
        #print(i, j, cost)
        #print(len(set(c[i])|set(c[j])))
        if len(set(c[i])|set(c[j]))==n:
            cost = a[i]+a[j] if (a[i]+a[j])<cost else cost
            
print(cost)

Submission status: Wrong Answer

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

a = []
b = []
c = {}
for i in range(m):
    _a, _b = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c[i] = list(map(int, input().split()))
    
inf = int(10e+6)

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

def rec(dp_i, cost):
    if dp[dp_i] > cost:
        dp[dp_i] = cost
        
    return

for _ci, _cv in c.items():
    now = 0
    for _v in _cv:
        now |= 1 << _v-1
    
    for bits in range(1 << n):
        rec(bits|now, dp[bits] + a[_ci])

        
print("="*20)
if dp[(1 << n) - 1] == inf:
    print(-1)
else:
    print(dp[(1 << n) - 1])

Submission status: Wrong Answer

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

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

max_index=2**N
INF=10**15

dp={}

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)
    dp[sums] = mon

for j in range(M):
    lists=list(dp.keys())
    for i in lists:
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        try:
            dp[new_i] = min(dp[new_i], cost) 
        except:
            dp[new_i]=cost
try:
    print(dp[max_index-1])
except:
    print(-1)

Submission status: Wrong Answer

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

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

max_index=2**N
INF=10**15

dp={}

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)
    dp[sums] = mon

for j in range(M):
    lists=list(dp.keys())
    for i in lists:
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        try:
            dp[new_i] = min(dp[new_i], cost) 
        except:
            dp[new_i] = cost

try:
    print(dp[max_index-1])
except:
    print(-1)

Submission status: Wrong Answer

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

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

max_index=2**N
INF=10**15

dp={}

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)
    dp[sums] = mon

for j in range(M):
    lists=list(dp.keys())
    for i in lists:
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = cost
        dp[new_i] = min(dp[new_i], cost) 

try:
    print(dp[max_index-1])
except:
    print(-1)

Submission status: Wrong Answer

Solution code:
# 所持している鍵の集合をbitで表現する
#　鍵の集合を表す2進数が少なくなる方向に遷移することはないから，for文for文でかける

N, M = map(int, input().split())
status_money = [float('inf')] * (1 << N)
key_money = []

# 初期状態からの遷移を記録
for _ in range(M) :
    a, b = map(int, input().split())
    key_money.append(a)
    C = 0
    for c in input().split() :
        C |= (1 << int(c) - 1)
    status_money[C] = a
    
# ある状態とある状態の組合せを全部取る
for c in range(1 << N):
    # どんな鍵の組合せでも到達できない宝箱の組合せがあるかもしれない
    if status_money[c] == float('inf'):
        continue
    for d in range(1 << N):
        # c と d の論理和をとって新しく生成される状態 e を考える
        e = c | d
        # eにあらかじめ格納されている最小コストと，今生成したコストとのminをとる
        status_money[e] = min(status_money[c] + status_money[d], status_money[e])

# そもそも到達できない場合の処理を記述       
if status_money[-1] == float('inf'):
    print(-1)
else:
    print(status_money[-1])

Submission status: Wrong Answer

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

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)
    
    
    temp= many_int()
    sums = 0
    for i in temp:
        sums = sums | i
    treasures.append(sums)

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

ok = 10**9
ng = 0

def can_open_all_treasures(money):
    total_cost = 0
    used_keys = []
    for treasure in treasures_list:
        if len(treasure) == 0:
            print(-1)
            exit()
        else:
            min_cost = 10**6
            for openable_key in treasure:
                if openable_key in used_keys:
                    min_cost = 0
                    continue
                else:
                    if keys_dic[openable_key] <= min_cost:
                        min_key = openable_key
                        min_cost = keys_dic[min_key]
                    # min_cost = min(keys_dic[openable_key], min_cost)
            total_cost += min_cost
            if min_cost != 0:
                used_keys.append(min_key)

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

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

print(ok)

Submission status: Wrong Answer

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

keys=[[] for i in range(N)] #宝箱iを開けるのに必要な鍵
keys_num=[0]*N
for i,c_list in enumerate(C):
    for c in c_list:
        keys[c-1].append(i+1)
        keys_num[c-1]+=1
if min(keys_num)==0:
    print(-1)
    exit()
    
    
keys2=[]
bought=[]
removed=set()
ans=0
while len(keys_num)>0:
    i=keys_num.index(min(keys_num))
    K=keys[i]
    index=min(K,key=lambda k:A[k-1])
    if index in bought:
        pass
    else:
        ans+=A[index-1]
        bought.append(index)
    keys2.append(keys.pop(i))
    keys_num.pop(i)
bought=set(bought)
K=len(keys2)
keys3=[]
for k in keys2:
    keys3.append(set(keys2[i]) & bought)
keys3 = sorted(keys3, key=len)
for j in range(N):
    i=0
    while i<K:
        if len(keys3[i]) > 1:
            index=min(list(keys3[i]),key=lambda k:A[k-1])
            keys3[i].discard(index)
            if not index in removed:
                removed.add(index)
                ans-=A[index-1]
        i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = []
d = [0 for _ in range(M)]
for i in range(M):
  ab.append(list(map(int, input().split())))
  for k in list(map(int, input().split())):
    d[i] += 2**(k-1)
  
infty = 10**8
  
dp = [infty for j in range(2**N)]
#i番目の鍵まで使って状態jにできる最小のコスト
dp[d[0]] = ab[0][0]

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

ans = dp[2**N-1] if dp[2**N-1] != infty else -1
print(ans)