Problem:


Score : 500 points

Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

All values in input are integers.

1 \leq N \leq 12

1 \leq M \leq 10^3

1 \leq a_i \leq 10^5

1 \leq b_i \leq N

1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}

Output

Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1.

Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

Sample Output 3

69942



Sample input:
2 3
10 1
1
15 1
2
30 2
1 2


Sample output:
25

Submission status: Wrong Answer

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

dp = [0]*(2**n)
len_dp = len(dp)

key_list = dict()
sub = 1
for i in range(n):
  key_list[i+1] = sub
  sub *= 2

for _ in range(m):
  a, b = map(int, input().split())
  c = [int(x) for x in input().split()]
  key = 0
  for value in c:
    key += key_list[value]
  for i in range(len_dp-1, -1, -1):
    if i == 0 or dp[i]:
      if dp[i|key]:
        dp[i|key] = min([dp[i]+a, dp[i|key]])
      else:
        dp[i|key] = dp[i]+a

print(dp[len_dp-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = []
c= []
keys = ["" for _ in range(m)]

for i in range(m):
    ab.append(list(map(int, input().split())))
    kari = list(map(int, input().split()))
    c.append(kari)
    for j in range(n):
        if j+1 in kari:
            keys[i] = keys[i]+"1"
        else:
            keys[i] = keys[i] + "0"
#%%
all_patterns = ["0","1"]
options = ["0", "1"]

for _ in range(n-1):
    all_patterns = [j+i for i in (options) for j in all_patterns]

dp_dict = dict()
for pattern in all_patterns:
    dp_dict[pattern] = 1e+10
dp_dict["0"*n] = 0

#%%
for key in dp_dict.keys():
    for j in range(m):
        if dp_dict[key]+ab[j][0] < dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")]:
            dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")] = dp_dict[key]+ab[j][0]

if dp_dict["1"*n] != 1e+10:
    print(dp_dict["1"*n])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n ,m= list(map(int,input().split()))
kagi = [[]for _ in range(m)] 
#a円　b種類開けられる
for i in range(m):
    a,b =  list(map(int,input().split()))
    X =  list(map(int,input().split()))
    bit = 0
    for x in X:
        bit |= 2**(x-1)
    kagi[i] = [a,bit]

ok = 2**n-1#全部空いたらこれ
kagi.sort()
aketa = 0
ans = 0
ng = 1
for i in range(m):
    if aketa == ok:
        ng = 0
        break
    for j in range(n):
        if kagi[i][1]>>j&1 ==1 and kagi[i][1]>>j&1 != aketa>>j&1:
            aketa |= kagi[i][1]
            ans += kagi[i][0]


if ng:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    key = [0]
    box = [0]
    for _ in range(M):
        k,_ = LI()
        key.append(k)
        b = 0
        for c in LI():
            b += 2**(c-1)
        box.append(b)

    dp = [[INF] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(1,M+1):
        for j in range(2**N):
            dp[i][j] = min(dp[i-1][j],dp[i-1][j - (j&box[i])]+key[i])
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy
input = sys.stdin.readline
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())
    for c in [int(i) for i in input().split()]:
        C[i] |= 1 << (c - 1)

dp = [[float("inf")] * 2 ** N for _ in range(2)]
dp[0][0] = 0
for i, c in enumerate(C):
    for bit in range(2 ** N):
        dp[1][c | bit] = min(dp[0][c | bit], dp[0][bit] + A[i], dp[1][c | bit])
    dp[0] = deepcopy(dp[1])
print(dp[0][-1] if dp[0][-1] < float("inf") else - 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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())
    for c in [int(i) for i in input().split()]:
        C[i] |= 1 << (c - 1)

dp = [[float("inf")] * 2 ** N for _ in range(2)]
dp[0][0] = 0
dp[1][0] = 0
for i, c in enumerate(C):
    for bit in range(2 ** N):
        dp[1][c | bit] = min(dp[0][c | bit], dp[0][bit] + A[i], dp[1][c | bit])
    dp[0], dp[1] = dp[1], dp[0]
print(dp[0][-1] if dp[0][-1] < float("inf") else - 1)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9
N, M = map(int,input().split())
dp = [[INF for i in range(1 << N)] for j in range(M+1)]
dp[0][0] = 0
for i in range(M):
    a, b = map(int,input().split())
    c = list(map(int,input().split()))
    k = 0
    for l in c:
        k += 1 << (l - 1)
    for j in range(1 << N):
        if dp[i][j] != INF:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j])
            dp[i+1][j | k] = min(dp[i][j | k], dp[i][j] + a)

if dp[M][1 << N - 1] == INF:
    print(-1)
else:
    print(dp[M][(1 << N) - 1])

Submission status: Wrong Answer

Solution code:



N,M=map(int, input().split())
key=[]
for i in range(M):
    a,b=map(int, input().split())
    C=list(map(int, input().split()))
    c=0
    for d in C:
        c+=2**(d-1)
    key.append((a,b,c))

dp=[10**8+10]*(2**N)
dp[0]=0
for bi in range(0,2**N):
    for i in range(M):
        t=key[i]
        a,b,c=t
        

        dp[bi|c]=min(dp[bi]+a,dp[bi|c])
if dp[-1]<=10**8+10:
    print(int(dp[-1]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N, M = map(int, input().split())
INF = 10**12
AB = []
C = []
for i in range(M):
    AB.append(tuple(int(x) for x in input().split()))
    C.append(sum(1<<(int(x)-1) for x in input().split()))

dp = [INF]*(1<<N)
dp[0] = 0
for i in range(1<<N):
    for (a, b), c in zip(AB, C):
        m = i | c
        dp[m] = min(dp[m], dp[i]+a)
        
if dp[N] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
INF = 10**12
AB = []
C = []
for i in range(M):
    AB.append(tuple(int(x) for x in input().split()))
    C.append(sum(1<<(int(x)-1) for x in input().split()))

dp = [INF]*(1<<N)
dp[0] = 0
for i in range(1<<N):
    for (a, b), c in zip(AB, C):
        m = i | c
        dp[m] = min(dp[m], dp[i]+a)
        
if dp[N] == INF:
    print(-1)
else:
    print(dp[(1<<N)-1])

Submission status: Wrong Answer

Solution code:
import copy
N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for v in range(2**N):
        for c in C:
            nv=copy.copy(v)
            bi=2**(c-1)
            if (v//bi)%2==0:
                nv+=bi
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    costs = [None]*m
    keys = [None]*m
    pattern = 2**n
    dp = [10**12]*pattern
    for i in range(m):
        costs[i] = int(input().split()[0])
        keys[i] = sum([1<<(int(i)-1) for i in input().split()])
    dp[0] = 0
    for i in range(pattern):
        for cost, key in zip(costs, keys):
            pi = i|key
            if dp[pi] > cost + dp[i]:
                dp[pi] = cost + dp[i]
    print(dp[pattern-1])
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def digit(n, m):
    n = str(n)
    while m - len(n):
        n = '0' + n
    return n

n, m = MAP()
dp = [[inf for _ in range(2 ** n)] for _ in range(m)]
for i in range(m):
    dp[i][0] = 0
for i in range(m):
    a, b = MAP()
    c = LIST()
    arr = [1 if i + 1 in c else 0 for i in range(n)]
    cbit = '0b'
    for j in range(n):
        cbit += str(arr[j])
    if i == 0:
        for j in range(1, 2 ** n):
            jbit = bin(j)
            debug(cbit, jbit, (int(cbit[2:], 2) ^ int(jbit[2:], 2)) & int(jbit[2:], 2) != 0)
            if (int(cbit[2:], 2) ^ int(jbit[2:], 2)) & int(jbit[2:], 2) != 0:
                continue
            dp[i][j] = a
    else:
        for j in range(1, 2 ** n):
            jbit = bin(j)
            debug(cbit, jbit)
            flag = False
            '''
            if (int(cbit[2:], 2) & int(jbit[2:], 2) != int(cbit[2:]):
                dp[i][j] = dp[i - 1][j]
                continue
            '''
            formerbit = bin(int(cbit[2:], 2) ^ int(jbit[2:], 2))
            debug(formerbit)
            former = int(formerbit[2:], 2)        
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][former] + a)
    debug(dp[i])
if dp[m - 1][2 ** n - 1] >= inf:
    print(-1)
else:
    print(dp[m - 1][2 ** n - 1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = cost[i]
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            k = int(key[j], 0)
            tar = k | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

n, m = MAP()
dp = [[inf for _ in range(2 ** n)] for _ in range(m + 1)]
for i in range(1, m + 1):
    dp[i][0] = 0
for i in range(1, m + 1):
    a, b = MAP()
    c = LIST()
    arr = [1 if i + 1 in c else 0 for i in range(n)]
    debug('arr', arr)
    if i == 1:
        for j in range(2 ** n):
            tmp = [int(k) for k in bin(j)[2:]]
            while n - len(tmp):
                tmp.insert(0, 0)
            debug('tmp', tmp)
            flag = True
            for k in range(n):
                if arr[k] == 0 and tmp[k] == 1:
                    flag = False
                    break
            if flag:
                dp[i][j] = a
    else:
        for j in range(2 ** n):
            tmp = [int(k) for k in bin(j)[2:]]
            while n - len(tmp):
                tmp.insert(0, 0)
            tmp2 = [0 if tmp[k] == 0 or arr[k] == 1 else 1 for k in range(n)]
            debug('tmp', tmp)
            debug('tmp2', tmp2)
            numtmp2 = 0
            for k in range(n):
                numtmp2 += tmp2[k] * (2 ** (n - k - 1))
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][numtmp2] + a)
    debug(dp[i])
debug('')
for i in range(m + 1):
    debug(dp[i])
if dp[m][2 ** n - 1] >= inf:
    print(-1)
else:
    print(dp[m][2 ** n - 1])

Submission status: Wrong Answer

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

dp = [[[float('inf'),0] for i in range(n+1)] for j in range(m+1)]

for i in range(1,m+1):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(1,n+1):
        if dp[i-1][j][0] <= dp[i][j][0]:
            dp[i][j] = dp[i-1][j]
        else:
            pass
        if j <= b:
            if dp[i-1][c[j-1]][0] <= a:
                dp[i][c[j-1]] = dp[i-1][c[j-1]]
            else:
                dp[i][c[j-1]] = [a, i]

ans = 0
dic = {}
for i in range(1,n+1):
    if dp[m][i][0] == float('inf'):
        ans = -1
        break
    if dp[m][i][1] not in dic.keys():
        dic[dp[m][i][1]] = 1
        ans += dp[m][i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
dp = [[10**9]*(2**n+5) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    res = 0
    for x in c:
        res|=1<<(x-1)
    for j in range(2**n):
        ni = i+1
        nj = j|res
        dp[ni][j] = min(dp[ni][j],dp[i][j])
        dp[ni][nj] = min(dp[ni][nj],dp[i][j]+a)
print(dp[m][2**n-1])

Submission status: Wrong Answer

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

dp = [[float('inf') for i in range(n+1)] for j in range(m+1)]

for i in range(1,m+1):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(1,n+1):
        dp[i][j] = min(dp[i-1][j], dp[i][j])
        if j <= b:
            dp[i][c[j-1]] = min(dp[i-1][c[j-1]], a)
ans = 0
dic = {}
for i in range(1,n+1):
    if dp[m][i] == float('inf'):
        ans = -1
        break
    if dp[m][i] not in dic.keys():
        dic[dp[m][i]] = 1
        ans += dp[m][i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
N, M = map(int, input().split())
inf = 10**18
dp = [inf]*(1<<N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    Cs = list(map(int, input().split()))
    bb = 0
    for c in Cs:
        bb += 2**(c-1)
    for x in range(1<<N -1, -1, -1):
        dp[bb|x] = min(dp[x]+a, dp[bb|x])

r = dp[(1<<N)-1]
if r != inf:
    print(dp[(1<<N)-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    ac = [[0, set()] for i in range(M)]
    for i in range(M):
        a, b = map(int, input().split())
        ac[i][1] = set(map(int, input().split()))
        ac[i][0] = a

    dp = [[-1, set()] for i in range(2**N)]
    dp[0][0] = 0

    cost = [[10**6, -1] for i in range(N)]
    for i in range(M):
        for x in ac[i][1]:
            if cost[x-1][0] > ac[i][0]:
                cost[x-1][0] = ac[i][0]
                cost[x-1][1] = i
    # print(cost)
    tmp = [2**i for i in range(N)]

    for i in range(1, 2**N):
        for j in range(N):
            if (i >> j) % 2 == 1:
                if dp[i-tmp[j]][0] < 0:
                    continue
                #print(i, j+1, dp[i - tmp[j]][1])
                if (j+1) in dp[i - tmp[j]][1]:
                    k = dp[i - tmp[j]][0]
                    if dp[i][0] > k or dp[i][0] == -1:
                        dp[i][0] = k
                        dp[i][1] = dp[i-tmp[j]][1]

                elif cost[j][1] >= 0:
                    k = dp[i - tmp[j]][0] + cost[j][0]
                    #print(i, k)
                    if dp[i][0] > k or dp[i][0] == -1:
                        dp[i][0] = k
                        dp[i][1] = set(dp[i-tmp[j]][1])
                        dp[i][1] |= ac[cost[j][1]][1]

    # print(dp)
    print(dp[2**N - 1][0])


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    ac = [[0, set()] for i in range(M)]
    for i in range(M):
        a, b = map(int, input().split())
        ac[i][1] = set(map(int, input().split()))
        ac[i][0] = a

    dp = [[-1, set()] for i in range(2**N)]
    dp[0][0] = 0

    cost = [[10**6, -1] for i in range(N)]
    for i in range(M):
        for x in ac[i][1]:
            if cost[x-1][0] > ac[i][0]:
                cost[x-1][0] = ac[i][0]
                cost[x-1][1] = i
    # print(cost)
    tmp = [2**i for i in range(N)]

    for i in range(1, 2**N):
        for j in range(N):
            if (i >> j) % 2 == 1:
                if dp[i-tmp[j]][0] < 0:
                    continue
                if j+1 in dp[i - tmp[j]][1]:
                    k = dp[i - tmp[j]][0]
                    if dp[i][0] > k:
                        dp[i][0] = k
                        dp[i][1] = dp[i-tmp[j]][1]

                elif cost[j][1] >= 0:
                    k = dp[i - tmp[j]][0] + cost[j][0]
                    #print(i, k)
                    if dp[i][0] > k or dp[i][0] == -1:
                        dp[i][0] = k
                        dp[i][1] = set(dp[i-tmp[j]][1])
                        dp[i][1] |= ac[cost[j][1]][1]

    # print(dp)
    print(dp[2**N - 1][0])


main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    inf=10**9
    n,m=MI()
    kk=[]
    aa=[]
    for _ in range(m):
        k=0
        a,b=MI()
        aa.append(a)
        cc=LI1()
        for c in cc:k|=1<<c
        kk.append(k)
    dp=[inf]*(1<<n)
    dp[0]=0
    for bit in range(1<<n):
        pre=dp[bit]
        if pre==inf:continue
        for a,k in zip(aa,kk):
            nb=bit|k
            dp[nb]=min(dp[nb],pre+a)
    print(dp[-1])

main()

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

n, m = MAP()
dp = [[inf, -1] for _ in range(n)]
alist = []
for i in range(m):
    a, b = MAP()
    alist.append(a)
    c = LIST()
    tmp = deepcopy(dp)
    tmplist = []
    for j in c:
        if dp[j - 1][0] == inf:
            dp[j - 1][0] = a
            dp[j - 1][1] = i
            continue
        if dp[j - 1][0] > a:
            tmplist.append(j - 1)
            tmp[j - 1][0] = a
            tmp[j - 1][1] = i
    l = list(set(c) & set(tmplist))
    past = sum([alist[j] for j in list(set([dp[i][1] for i in l]))])
    now = sum([alist[j] for j in list(set([tmp[i][1] for i in l]))])
    debug(past, now)
    if past > now:
        dp = tmp
    debug(dp)
arr = list(set([dp[i][1] for i in range(n)]))
ans = 0
for i in arr:
    if i == -1:
        print(-1)
        exit()
    ans += alist[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
N=[10**9]*n
s=set()
for i in range(m):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    if sum(set([N[c-1] for c in C]))>a:
        for c in C:
            N[c-1]=a
            s.add(c)
if len(s)!=n:
    print(-1)
else:
    print(sum(set(N)))

Submission status: Wrong Answer

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    if N==12:
        exit()
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append((s,a))


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s,a=key[i]
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])


if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

def solve(i, cost, keybit):
    if i==m:
        return 10**7
    if mem[i][keybit] is not None:
        return mem[i][keybit]
    if keybit|keys[i][1]==2**n-1:
        ans = cost+keys[i][0]
    else:
        ans = solve(i+1, cost+keys[i][0], keybit|keys[i][1])
    ans = min(ans, solve(i+1, cost, keybit))
    mem[i][keybit] = ans
    return ans

mem = [[None]*(2**n) for _ in range(m)]
ans = solve(0, 0, 0)
print(ans if ans<10**7 else -1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    keys.append((a, c))


def solve(i, cost, key_set):
    if i==m:
        return 10**7
    if mem[i] is not None:
        return mem[i]
    if len(key_set|keys[i][1])==n:
        ans = cost+keys[i][0]
    else:
        ans = solve(i+1, cost+keys[i][0], key_set|keys[i][1])
    ans = min(ans, solve(i+1, cost, key_set))
    mem[i] = ans
    return ans

mem = [None]*m
ans = solve(0, 0, set())
print(ans if ans<10**7 else -1)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
dp = [float('inf')] * (2 ** n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    c = sum(1 << (i - 1) for i in map(int, input().split()))
    for j in range(2 ** n):
        if dp[c | n] > dp[j] + a:
            dp[c | n] = dp[j] + a

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

Submission status: Wrong Answer

Solution code:

N, M = map(int, input().rstrip().split())
INF = int(1e18)

abc = []
for _ in range(M):
    a, b = map(int, input().rstrip().split())
    c = list(map(int, input().rstrip().split()))
    abc.append([a, b, c])
    
#dp = [[-1] * 2 ** (N + 1) for _ in range(M + 1)]
dp = [[INF] * 2 ** (N + 1) for _ in range(2)]

for i in range(M):
    mask = 0
    for c in abc[i][2]:
        mask += 2 ** (c - 1)

    for j in range(2 ** (N + 1)):
        dp[i%2][j] = dp[(i+1)%2][j]

    if dp[i%2][mask] == INF:
        dp[i%2][mask] = abc[i][0]
        
    for j in range(2 ** (N + 1)):
        if dp[(i+1)%2][j] != INF:
            dp[i%2][j|mask] = min(dp[i%2][j|mask], dp[(i+1)%2][j] + abc[i][0])
    
if dp[i%2][2**N-1] == INF:
    print(-1)
else:
    print(dp[i%2][2**N-1])

Submission status: Wrong Answer

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

n, m = [int(x) for x in input().split()]
items = []
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    c_ = sum([1 << (x - 1) for x in c])
    items.append([a, c_])

dp = [[float("inf")]*2**n for _ in range(m + 1)]
dp[0][0] = 0

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

ans = float("inf")

for i in range(1, m + 1):
    ans = min(ans, dp[i][-1])

if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

n, m = [int(x) for x in input().split()]
items = []
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    c_ = sum([1 << (x - 1) for x in c])
    items.append([a, c_])

dp = [[float("inf")]*2**n for _ in range(m + 1)]
dp[0][0] = 0

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

ans = float("inf")

for i in range(1, m + 1):
    ans = min(ans, dp[i][-1])

print(ans)

Submission status: Wrong Answer

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

n, m = [int(x) for x in input().split()]
keys = {}
items = [0]*n
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    keys[a] = c
    for x in c:
        items[x - 1] += 1

for i in items:
    if i == 0:
        print(-1)
        sys.exit()

keys_key = keys.keys()
keys_key = sorted(keys_key, reverse=True)

ans = sum(keys_key)
from copy import deepcopy
items2 = deepcopy(items)
ans2 = ans

for i in keys_key:
    c_ = keys[i]
    flag = 1
    for j in c_:
        if items[j - 1] <= 1:
            flag = 0
    if flag:
        for j in c_:
            items[j - 1] -= 1
        ans -= i

for i in keys_key[::-1]:
    c_ = keys[i]
    flag = 1
    for j in c_:
        if items2[j - 1] <= 1:
            flag = 0
    if flag:
        for j in c_:
            items2[j - 1] -= 1
        ans2 -= i
print(min(ans, ans2))

Submission status: Wrong Answer

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

n, m = [int(x) for x in input().split()]
keys = {}
items = [0]*n
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    keys[a] = c
    for x in c:
        items[x - 1] += 1

for i in items:
    if i == 0:
        print(-1)
        sys.exit()

keys_key = keys.keys()
keys_key = sorted(keys_key, reverse=True)

ans = sum(keys_key)

for i in keys_key:
    c_ = keys[i]
    flag = 1
    for j in c_:
        if items[j - 1] <= 1:
            flag = 0
    if flag:
        for j in c_:
            items[j - 1] -= 1
        ans -= i

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

inf = 10 ** 8


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

def tolist(n):
    nn = n
    ret = [0] * N
    for i in range(N):
        ret[i] = nn % 2
        nn //= 2
    return ret

def tonum(l):
    ret = 0
    for i in range(N):
        ret += l[i] * (2**i)
    return ret

def union(l1,l2):
    ret = [0] * N
    for i in range(N):
        ret[i] = min(l1[i] + l2[i],1) 
    return tonum(ret)



cost = [0] * M
data = [[0]*N for i in range(M)]

for i in range(M):
    a,b = map(int,input().split())
    cost[i] = a
    c = list(map(int,input().split()))
    for x in c:
        x -= 1
        data[i][x] = 1

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

for j in range(2**N):
    if union(tolist(j),data[0]) == tonum(data[0]):
        dp[j] = cost[0]

for i in range(1,M):
    #print(dp)
    for j in range(2**N):
        #print(dp)
        ###このjは一つ前のiのものであることに注意
        l = tolist(j)
        dp[union(l,data[i])] = min(dp[union(l,data[i])], dp[union(l,data[i])], dp[j]+cost[i])
        

#print(dp)
if dp[2**N -1] == inf:
    print(-1)
else:
    print(dp[2**N -1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
A=[0]*m
B=[0]*m
C=[[] for _ in range(m)]
def func(a):
    A=int(a)
    return 1<<(A-1)
for i in range(m):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
    c=list(map(func,input().split()))
    C[i]=c
#dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi=10**20
dp=[[infi for i in range(2**n+1)]for _ in range(m+1)]
dp[0][0]=0
for i in range(m):
    for s in range(2**(n-1)):
        ni=i+1
        ns=s
        #使わないとき
        dp[ni][ns]=min(dp[i][s], dp[ni][ns])
        #使うとき
        for c in C[i]:
            ns = s | c
        dp[ni][ns]=min(dp[ni][ns], dp[i][s]+A[i])
ans=dp[m][2**n-1]
print(ans if ans<infi else -1)