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: Time Limit Exceeded

Solution code:
n,m = map(int,raw_input().split())
keys = [0]*m
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	keys[i] = (mask,a)

dp = []
M = 1<<n
for i in xrange(m+1):
	dp.append([10**9]*M)
	dp[i][0] = 0
	
for i in xrange(m):
	key = keys[i]
	for j in xrange(M):
		k = j|keys[i][0]
		dp[i+1][k] = min(dp[i+1][k], dp[i][j]+keys[i][1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
 
if dp[m][M-1] >= 10**9:
	print -1
else:
	print dp[m][M-1]

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
dp_1 = [float("inf")] * (2**n)
dp_2 = [float("inf")] * (2**n)
dp_1[0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        if i % 2 == 0:
            dp_2[j|c] = min(dp_1[j|c], dp_1[j] + a, dp_2[j|c])
            dp_2[j] = min(dp_1[j], dp_2[j])
        else:
            dp_1[j|c] = min(dp_2[j|c], dp_2[j] + a, dp_1[j|c])
            dp_1[j] = min(dp_2[j], dp_1[j])

print([dp_1[-1], -1][dp_1[-1] == float("inf")])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,raw_input().split())
keys = []
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	keys.append((mask,a))

dp = []
M = 1<<n
for i in xrange(m+1):
	dp.append([10**9]*M)
	dp[i][0] = 0
	
for i in xrange(m):
	key = keys[i]
	for j in xrange(M):
		k = j|keys[i][0]
		dp[i+1][k] = min(dp[i+1][k], dp[i][j]+keys[i][1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
 
if dp[m][M-1] >= 10**9:
	print -1
else:
	print dp[m][M-1]

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
dp_1 = [float("inf") for i in range(2**n)]
dp_2 = [float("inf") for i in range(2**n)]
dp_1[0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        if i % 2 == 0:
            dp_2[j|c] = min(dp_1[j|c], dp_1[j] + a, dp_2[j|c])
            dp_2[j] = min(dp_1[j], dp_2[j])
        else:
            dp_1[j|c] = min(dp_2[j|c], dp_2[j] + a, dp_1[j|c])
            dp_1[j] = min(dp_2[j], dp_1[j])

print([dp_1[-1], -1][dp_1[-1] == float("inf")])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,raw_input().split())
keys = []
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 2**(x-1)
	keys.append((mask,a))
#print(keys)
dp = []
M = 2**n
for i in xrange(m+1):
	dp.append([10**9]*M)
	dp[i][0] = 0
	
for i in xrange(m):
	key = keys[i]
	for j in xrange(M):
		dp[i+1][j|key[0]] = min(dp[i+1][j|key[0]], dp[i][j]+key[1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])

if dp[m][M-1] >= 10**9:
	print -1
else:
	print dp[m][M-1]

Submission status: Time Limit Exceeded

Solution code:
#python 3
n,m = map(int,input().split())
keys = []
for i in range(m):
	a,b = map(int,input().split())
	c = map(int,input().split())
	mask = 0
	for x in c:
		mask += 2**(x-1)
	keys.append((mask,a))
#print(keys)
dp = []
M = 2**n
for i in range(m+1):
	dp.append([10**10]*(M))

for i in range(m+1):
	dp[i][0] = 0
	
for i in range(m):
	key = keys[i]
	for j in range(M):
		dp[i+1][j|key[0]] = min(dp[i+1][j|key[0]], dp[i][j]+key[1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])

if dp[m][M-1] > 10**9:
	print(-1)
else:
	print(dp[m][M-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
dp_prev = [float("inf") for i in range(2**n)]
dp_next = [float("inf") for i in range(2**n)]
dp_prev[0] = 0
s = {0}

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    s_next = set()

    for j in s:
        dp_next[j|c] = min(dp_prev[j|c], dp_prev[j] + a, dp_next[j|c])
        dp_next[j] = min(dp_prev[j], dp_next[j])
        s_next.add(j|c)

    dp_prev = dp_next[:]
    s |= s_next

print([dp_next[-1], -1][dp_next[-1] == float("inf")])

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
dp_prev = [float("inf") for i in range(2**n)]
dp_next = [float("inf") for i in range(2**n)]
dp_prev[0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp_next[j|c] = min(dp_prev[j|c], dp_prev[j] + a, dp_next[j|c])
        dp_next[j] = min(dp_prev[j], dp_next[j])
    dp_prev = dp_next[:]


print([dp_next[-1], -1][dp_next[-1] == float("inf")])

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(item) for item in input().split()]
INF = 10 ** 10
dp = [INF] * (2 ** n)
dp[0] = 0
for i in range(m):
    a, b = [int(item) for item in  input().split()]
    c = [int(item) - 1 for item in  input().split()]
    bit = 0
    for item in c:
        bit |= 1 << item
    for j in range(2 ** n):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

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

inf = 1e9+7
dp = [inf] * (1 << N)
dp[0] = 0

for m in range(M):
    a, b = map(int, input().split())

    hako = list(map(int, input().split()))

    mask = sum(1 << (c-1) for c in hako)

    for i in range(1 << N):
        dp[i | mask] = min(dp[i | mask], dp[i] + a)

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
A = []
comp = sum(10**(x-1) for x in range(1,N+1))
for m in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  box = sum(10**(x-1) for x in c)
  A.append([box, a])
  ci = len(A)-1
  for i in range(0,len(A)-1):
    A.append([A[0|i][0] + A[ci][0], 
              A[0|i][1] + A[ci][1]])

if max([A[x][1] for x in range(len(A))]) >= comp:
  ans = min([A[x][1] for x in range(len(A))
           if len(str(A[x][0]).replace('0','')) >= len(str(comp))] )
else:
  ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

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

print([dp[-1][-1], -1][dp[-1][-1] == float("inf")])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n,m = map(int,input().split())
    boxes = [[]for _ in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        cs = list(map(lambda x: int(x)-1,input().split()))
        c = [0 for _ in range(n)]
        for i in cs:
            c[i]=1
        for i in cs:
            boxes[i].append((c,a))
    
    
    if not all([x for x in boxes]):
        print(-1)
        exit()
        
    union ={tuple([0 for _ in range(n)]):0}
    for i,box in enumerate(boxes):
        union2 ={}
        for c2,a2 in union.items():
            if c2[i]:
                union2[c2]=a2
        for c1,a1 in box:
            for c2,a2 in union.items():
                c3 = tuple(np.logical_or(c1, c2))
                a3 = a1 + a2
                if not c3 in union2:
                    union2[c3] = a3
                elif a3 < union2[c3]:
                    union2[c3] = a3
        union = union2
    alltrue = tuple([True for _ in range(n)])
    print(union[alltrue])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
n,m = map(int,input().split())
boxes = [[]for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    cs = list(map(lambda x: int(x)-1,input().split()))
    c = [0 for _ in range(n)]
    for i in cs:
        c[i]=1
    boxes[min(cs)].append((c,a))


union ={tuple([0 for _ in range(n)]):0}
for i,box in enumerate(boxes):
    union2 ={}
    for c2,a2 in union.items():
        if c2[i]:
            union2[c2]=a2
    for c1,a1 in union.items():
        for c2,a2 in union.items():
            c3 = tuple(np.logical_or(c1, c2))
            a3 = a1 + a2
            if not c3 in union2:
                union2[c3] = a3
            elif a3 < union2[c3]:
                union2[c3] = a3
    for c1,a1 in box:
        for c2,a2 in union.items():
            c3 = tuple(np.logical_or(c1, c2))
            a3 = a1 + a2
            if not c3 in union2:
                union2[c3] = a3
            elif a3 < union2[c3]:
                union2[c3] = a3
    union = union2
alltrue = tuple([True for _ in range(n)])
if alltrue in union:
    print(union[alltrue])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())

    INF = 10e7
    dp = [INF] * (1 << n)
    dp[0] = 0

    for _ in [0] * m:
        cost, _ = map(int, input().split())
        key = sum([1 << (int(i) - 1) for i in input().split()])

        for i in range(1 << n):
            new_cost = dp[i] + cost
            new_key = i | key
            dp[new_key] = min(dp[new_key], new_cost)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m = map(int,input().split())
boxes = [[]for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    cs = list(map(lambda x: int(x)-1,input().split()))
    c = [0 for _ in range(n)]
    for i in cs:
        c[i]=1
    for i in cs:
        boxes[i].append((c,a))
if not all([x for x in boxes]):
    print(-1)
    exit()
    
union ={tuple([0 for _ in range(n)]):0}
for i,box in enumerate(boxes):
    union2 ={}
    for c2,a2 in union.items():
        if c2[i]:
            union2[c2]=a2
    for c1,a1 in box:
        for c2,a2 in union.items():
            c3 = tuple(np.logical_or(c1, c2))
            a3 = a1 + a2
            if not c3 in union2:
                union2[c3] = a3
            elif a3 < union2[c3]:
                union2[c3] = a3
    union = union2
alltrue = tuple([True for _ in range(n)])
print(union[alltrue])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m = map(int,input().split())
boxes = [[]for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    cs = list(map(lambda x: int(x)-1,input().split()))
    c = [0 for _ in range(n)]
    for i in cs:
        c[i]=1
    for i in cs:
        boxes[i].append((c,a))
if not all([x for x in boxes]):
    print(-1)
    exit()
    
union ={tuple([0 for _ in range(n)]):0}
for i in range(n):
    boxes[i].append(([0 for _ in range(n)],0))
for box in boxes:
    union2 ={}
    for c1,a1 in box:
        for c2,a2 in union.items():
            c3 = tuple(np.logical_or(c1, c2))
            a3 = a1 + a2
            if not c3 in union2:
                union2[c3] = a3
            elif a3 < union2[c3]:
                union2[c3] = a3
    union = union2
alltrue = tuple([True for _ in range(n)])
print(union[alltrue])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m = map(int,input().split())
boxes = [[]for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    cs = list(map(lambda x: int(x)-1,input().split()))
    c = [0 for _ in range(n)]
    for i in cs:
        c[i]=1
    for i in cs:
        boxes[i].append((c,a))
if not all([x for x in boxes]):
    print(-1)
    exit()
    
union ={tuple([0 for _ in range(n)]):0}
for i in range(n):
    boxes[i].append(([0 for _ in range(n)],0))
for box in boxes:
    union2 ={tuple([0 for _ in range(n)]):0}
    for c1,a1 in box:
        for c2,a2 in union.items():
            c3 = tuple(np.logical_or(c1, c2))
            a3 = a1 + a2
            if not c3 in union2:
                union2[c3] = a3
            elif a3 < union2[c3]:
                union2[c3] = a3
    union = union2
alltrue = tuple([True for _ in range(n)])
print(union[alltrue])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = np.full(1 << n, INF, dtype=int)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    mask = sum(1 << box for box in boxes)
    
    for i in range(1 << n):
        if dp[i] + cost < dp[i | mask]:
            dp[i | mask] = dp[i] + cost

res = dp[-1] if dp[-1] != INF else -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = np.full(1 << n, INF, dtype=int)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    mask = sum(1 << box for box in boxes)
    
    for i in range(1 << n):
        dp[i | mask] = min(
                dp[i | mask],
                dp[i] + cost
            )

res = dp[-1] if dp[-1] != INF else -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = np.full(1 << n, INF, dtype=int)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    for box in boxes:
        mask |= 1 << box
    
    for i in range(1 << n):
        dp[i | mask] = min(
                dp[i | mask],
                dp[i] + cost
            )

res = dp[-1] if dp[-1] != INF else -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n, m = [int(x) for x in input().split()]

costs = []
masks = []

for _ in range(m):
    costs.append(int(input().split()[0]))

    boxes = {int(x)-1 for x in input().split()}
    mask = ['1' if idx in boxes else '0' for idx in range(n)][::-1]
    mask = int(''.join(mask), 2)
    masks.append(mask)

INF = int(10e8 + 1)
dp = np.full(1 << n, INF, dtype=int)
dp[0] = 0

for j in range(m):
    for i in range(1 << n):
        dp[i | masks[j]] = min(
                dp[i | masks[j]],
                dp[i] + costs[j]
            )

res = dp[-1] if dp[-1] != INF else -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
def e_get_everything(INF=float('inf')):
    # 参考: http://drken1215.hatenablog.com/entry/2019/09/29/103500
    N, M = [int(i) for i in input().split()]
    A, B, C = [], [], []
    for _ in range(M):
        a, b = [int(i) for i in input().split()]
        A.append(a)
        B.append(b)
        # 開けられる宝箱の集合Cはビット列に変換しておく
        C.append(sum(1 << (t - 1) for t in [int(i) for i in input().split()]))

    # dp[i][S]: i番目まで(i番は含まない)の鍵からいくつか選んで、
    # 開いた宝箱の集合がS(ビット列で表す)で表されるような場合にかかる費用の最小値
    dp = [[INF] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0  # 鍵を選ばず、開ける宝箱がないとき、費用は0とする

    for i in range(M):
        for j in range(1 << N):
            # i番目の鍵を使わない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i番目の鍵を使う場合
            next_j = j | C[i]  # C[i] で指定される宝箱(のいくつか)が新たに開く
            dp[i + 1][next_j] = min(dp[i + 1][next_j], dp[i][j] + A[i])
    # M個の鍵を使ってすべての宝箱を開けるとき、費用が有限値に更新されたか？
    return dp[M][(1 << N) - 1] if dp[M][(1 << N) - 1] != INF else -1

print(e_get_everything())

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = []
C = []
for i in range(M):
    a,b = map(int,input().split())
    tmp = sum([1<<(int(i)-1) for i in input().split()])
    A.append(a)
    C.append(tmp)

dp = [float('inf')] * (2**N)
dp[0] = 0
for i in range(2**N):
    for j in range(M):
        k = i | C[j]
        dp[k] = min(dp[k],dp[i]+A[j])
if dp[2**N-1]==float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = []
B =[]
C = []
for i in range(M):
    a,b = map(int,input().split())
    tmp = sum([1<<(int(i)-1) for i in input().split()])
    A.append(a)
    B.append(b)
    C.append(tmp)

dp = [float('inf')] * (2**N)
dp[0] = 0
for i in range(2**N):
    for j in range(M):
        k = i | C[j]
        dp[k] = min(dp[k],dp[i]+A[j])
if dp[2**N-1]==float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = []
B =[]
C = []
for i in range(M):
    a,b = map(int,input().split())
    tmp = [1<<(int(i)-1) for i in input().split()]
    A.append(a)
    B.append(b)
    C.append(sum(tmp))

dp = [float('inf') for _ in range(2**N)]
dp[0] = 0
for i in range(2**N):
    for j in range(M):
        k = i | C[j]
        dp[k] = min(dp[k],dp[i]+A[j])
if dp[2**N-1]==float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ab_list = []
c_bit_list = []
INF = 1000000000
for _ in range(M):
    a,b = list(map(int,input().split()))
    ab_list.append([a,b])
    c=0
    c_in = list(map(int,input().split()))
    for k in range(b):
        c |= 1<<(c_in[k]-1)
    c_bit_list.append([c,a])

dp_all_number = pow(2,N)
c_bit_list_len = len(c_bit_list)
dp = [INF for _ in range(dp_all_number)]
dp[0] = 0

for i in range(dp_all_number):
    for j in range(c_bit_list_len):
        #print(i,j)
        dp[i | c_bit_list[j][0]] = min(dp[i | c_bit_list[j][0]],dp[i]+c_bit_list[j][1])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

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

inf=10**8

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

A=[]
C=[]
dp=[inf]*(1<<n)
dp[0]=0

for _ in range(m):
  a,_=map(int,input().split())
  c=list(map(int,input().split()))
  A.append(a)
  tmp=0
  for i in c:
    tmp+=1<<(i-1)
  C.append(tmp)

for i in range(1<<n):
  for index,j in enumerate(C):
    dp[i|j]=min(dp[i|j],dp[i]+A[index])
ans=dp[-1]
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf=10**8

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

A=[]
C=[]
dp=[inf]*(1<<n)
dp[0]=0

for _ in range(m):
  a,_=map(int,input().split())
  c=list(map(int,input().split()))
  A.append(a)
  tmp=0
  for i in c:
    tmp+=1<<(i-1)
  C.append(tmp)

for i in range(1<<n):
  for index,j in enumerate(C):
    dp[i|j]=min(dp[i|j],dp[i]+A[index])
ans=dp[-1]
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

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

D=[{}for i in range(N+1)]
z=[0 for i in range(N)]
D[0][tuple(z)]=0

L=[]
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=[0 for i in range(N)]
    for j in range(N):
        if j+1 in c:
            d[j]=1
    L.append([d,a])
#print(L)

for i in range(N):
    for j in D[i]:
        #print(D[i][j])
        for k in L:
            d=[]
            for l in range(N):
                if j[l]==0 and k[0][l]==0:
                    d.append(0)
                else:
                    d.append(1)
            #print(d)
            if tuple(d) not in D[sum(d)]:
                D[sum(d)][tuple(d)]=D[i][j]+k[1]
            else:
                if D[sum(d)][tuple(d)]>D[i][j]+k[1]:
                    D[sum(d)][tuple(d)]=D[i][j]+k[1]
ans=[1 for i in range(N)]
if tuple(ans) not in D[N]:
    print(-1)
else:
    print(D[N][tuple(ans)])

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    for cc in c:
        C[i] += (1<<(cc-1)) # bit

dp = [[MAX]*(2**N) for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
#    for p in range(M):
#        print(dp[p])
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j|C[i]] = min(dp[i+1][j|C[i]], dp[i][j]+ab[i][0])

res = dp[-1][-1]
if res == MAX:
    print(-1)
else:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
dp = [float("inf")]*(2**n)
dp[0] = 0
for M in range(m):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))

    state = 0
    for c in C:
        state += 2**(c-1)

    for i in range(2**n):
        if dp[i] != float("inf"):
            dp[i|state] = min(dp[i]+a,dp[i|state])

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
dp = [float("inf")]*(2**n)
dp[0] = 0
for M in range(m):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))

    state = 0
    for c in C:
        state += 2**(c-1)

    for i in range(2**n):
        if dp[i|state] != float("inf"):
            dp[i|state] = min(dp[i]+a,dp[i|state])
        else:
            dp[i|state] = dp[i]+a

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
price = []
keys = []
dp = [float('inf') for i in range(1<<N)]
dp[0] = 0
for k in range(M):
    price.append(int(input().split()[0]))
    keys.append(list(map(int,input().split())))
for p,key in zip(price,keys):
    key_open = 0
    for k in key:
        key_open |= 1 << (k-1)
        for j in range(1 << N):
            dp[j|key_open] = min(dp[j|key_open], dp[j] + p)

if dp[(1<<N)-1] == float('inf'):
    dp[(1<<N)-1] = - 1
print(dp[(1 << N) - 1])

Submission status: Time Limit Exceeded

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


import numpy as np

N,M=acinput()

key=[]
for i in range(M):
    a,b=acinput()
    c=acinput()
    tmp=0
    for sc in c:
        tmp=tmp|(1<<(sc-1))
    key.append({"open":tmp,"cost":a})

dp=[float("inf") for i in range(2**N)]
dp[0]=0

for s in range(1<<N):
    for sk in key:
        t=s|sk["open"]
        #print(bin(t))
        dp[t]=min(dp[t],dp[s]+sk["cost"])

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [0]*M
b = [0]*M
c = [[] for _ in range(M)]
for i in range(M):
    a[i],b[i] = map(int,input().split())
    c[i] = list(map(int,input().split()))
    
inf = 2**30 - 1
dp = [[inf]*(2**N+1) for _ in range(M+1)]
dp[0][0] = 0

c_bit = [0] * M
for i in range(M):
    for t in c[i]:
        c_bit[i] += 1<<(t-1)

for i in range(M):
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][j|c_bit[i]] = min(dp[i+1][j|c_bit[i]],dp[i][j]+a[i])

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

Submission status: Time Limit Exceeded

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

dp = [float('inf') for _ in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    k = 0
    p = 1
    for x in c:
        k += 2 ** (x-1)
    for j in range(2 ** n):
        L = j | k
        dp[L] = min(dp[L], dp[j] + a)

#print(dp)

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

Submission status: Time Limit Exceeded

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

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


dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum(1 << (i - 1) for i in map(int, input().split()))
    for x in range(2 ** N):
        dp[c | x] = min(dp[c | x], dp[x] + a)

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

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(s) for s in input().split()]
key=[]
for i in range(m):
  cost,b=[int(s) for s in input().split()]
  op=0
  for i in input().split():
    op+=1<<(int(i)-1)
  key.append([cost,op])
N=2**n
dp=[[10**7 for _ in range(N)] for _ in range(m)]
dp[0][key[0][1]]=key[0][0]
dp[0][0]=0
for i in range(1,m):
  ls=[set() for _ in  range(N)]
  for j in range(N):
    ls[j].add(dp[i-1][j])
    ls[j].add(dp[i][j])
    x=j|key[i][1]
    ls[x].add(dp[i-1][j]+key[i][0])
  dp[i]=[min(ls[k]) for k in range(N)]
if dp[m-1][N-1]==10**7:
  print(-1)
else:
  print(dp[m-1][N-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(s) for s in input().split()]
key=[]
for i in range(m):
  cost,b=[int(s) for s in input().split()]
  op=0
  for i in input().split():
    op+=1<<(int(i)-1)
  key.append([cost,op])
N=2**n
dp=[[10**7 for _ in range(N)] for _ in range(m)]
dp[0][key[0][1]]=key[0][0]
dp[0][0]=0
for i in range(1,m):
  for j in range(N):
    dp[i][j]=min([dp[i-1][j],dp[i][j]])
    x=j|key[i][1]
    dp[i][x]=min([dp[i][x],dp[i-1][j]+key[i][0]])
if dp[m-1][N-1]==10**7:
  print(-1)
else:
  print(dp[m-1][N-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(s) for s in input().split()]
key=[]
for i in range(m):
  cost,b=[int(s) for s in input().split()]
  op=0
  for i in input().split():
    op+=1<<(int(i)-1)
  key.append([cost,op])
N=2**n
dp=[[10**7 for _ in range(N)] for _ in range(m)]
dp[0][key[0][1]]=key[0][0]
for i in range(1,m):
  for j in range(N):
    dp[i][j]=dp[i-1][j]
  dp[i][key[i][1]]=min([dp[i-1][key[i][1]],key[i][0]])
  for j in range(N):
    x=j|key[i][1]
    if dp[i][x]!=-1:
      dp[i][x]=min([dp[i][x],dp[i-1][j]+key[i][0]])
if dp[m-1][N-1]==10**7:
  print(-1)
else:
  print(dp[m-1][N-1])

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

N, M = map(int, input().split())
keys = []
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  cb = reduce(lambda x,y: x+2**(y-1),c,0)
  keys.append([a,cb])

INF = 10**9
dp = [INF]*5000
dp[0] = 0
for i in range(M):
  now = keys[i][1]
  a = keys[i][0]
  for j in range(2**N):
    dp[now | j] = min([dp[now | j], dp[j]+a])
if dp[2**N-1] == INF: dp[2**N-1] = -1
print(dp[2**N-1])

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

N, M = map(int, input().split())
keys = []
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  cb = reduce(lambda x,y: x+2**(y-1),c,0)
  keys.append([a,cb])

INF = 10**9
dp = [INF]*5000
dp[0] = 0
for i in range(M):
  now = keys[i][1]
  for j in range(2**N):
    dp[now | j] = min([dp[now | j], dp[j]+keys[i][0]])
if dp[2**N-1] == INF: dp[2**N-1] = -1
print(dp[2**N-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().strip().split(" ")))
keys=[]
want=2**N-1
for _ in range(M):
    a,b=list(map(int,input().strip().split(" ")))
    c=list(map(int,input().strip().split(" ")))
    temp=0
    for i in c:
        temp+=2**(i-1)
    keys+=[(a,temp)]

dp=[float("inf")]*(2**N)
dp[0]=0
for i in range(len(dp)):
    for j in range(len(keys)):
        price,val=keys[j]
        if i&val==0:
            continue
        dp[i]=min(dp[i-(i&val)]+price,dp[i])
        #print(keys[j])
        #print(dp[i],i,i&val)        
#print(keys)
#print(dp)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- Coding: utf-8 -*-
n, m = map(int, input().split())
INF = 1001001001
key_list = []
cost_list = []
for i in range(m):
  a, b = map(int, input().split())
  cost_list.append(a)
  c = list(map(int, input().split()))
  s = 0
  for j in range(b):
    s |= 1 << c[j] - 1
  key_list.append(s)
   
dp = [INF] * (1 << n)
dp[0] = 0
for s in range(1 << n):
  for i in range(m):
    t = s | key_list[i]
    cost = dp[s] + cost_list[i]
    dp[t] = min(cost, dp[t])
if dp[-1] == INF:
  ans = -1
else:
  ans = dp[-1]
print(ans)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで考えて、集合jの宝箱を開けるための最小コスト
dp = list2d(M+1, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
        dp[i+1][j|s] = min(dp[i+1][j|s], dp[i][j]+c)
ans = dp[M][-1]

if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m= list(map(int, input().split()))
key=[]
for i in range(m):
    a,b= list(map(int, input().split()))
    c= list(map(int, input().split()))
    s=0
    for j in range(b):
        s|=1<<c[j]-1
    tmp=[s,a]
    key.append(tmp)
inf=1001001001
dp=[inf for _ in range(1<<n)]
dp[0]=0
for s in range(1<<n):
    for i in range(m):
        t = s|key[i][0]
        cost=dp[s]+key[i][1]
        dp[t]=min(dp[t],cost)
ans=dp[-1]
if ans==inf:
    ans=-1
print(ans)