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, input().split())
op, keys, keyskey = 0, [10000000] * (2**N + 1), set()
for i in range(M):
    a, b = map(int, input().split())
    key = 0
    for x in set(map(int, input().split())):
        key += 2 ** (x-1)
    op |= key
    if keys[key] > a:
        keys[key] = a
        keyskey.add(key)

if op != 2**N - 1:
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keyskey))]
i, l = keyskey.pop(), 0
dp[0][i] = keys[i]

for i in keyskey:
    l += 1
    v = keys[i]
    dp[l][i] = min(v, dp[l-1][i])
    for j in range(1, 2**N):
        if dp[l-1][j] != 10000000:
            if dp[l][i | j] == 10000000:
                dp[l][i | j] = min(dp[l-1][i | j] , dp[l-1][j] + v)
            else:
                dp[l][i | j] = min(dp[l][i | j], dp[l-1][j] + v)

            if dp[l][j] == 10000000:
               dp[l][j] = dp[l-1][j]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = list(map(int, input().strip().split()))
    mask = 0
    for i in c:
        mask += 2**(i - 1)

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

print(dp[2**n - 1] if dp[2**n - 1] < float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = list(map(int, input().strip().split()))
    mask = 0b0
    for i in c:
        mask |= 0b1 << (i - 1)

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

print(dp[(1 << n) - 1] if dp[(1 << n) - 1] < float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = list(map(int, input().strip().split()))
    mask = 0b0
    for i in c:
        mask |= 0b1 << (i - 1)

    for j in range(1 << n):
        if dp[j] < float('inf'):
            dp[j | mask] = min(dp[j] + a, dp[j | mask])

print(dp[(1 << n) - 1] if dp[(1 << n) - 1] < float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = 0, [10000000] * (2**N + 1)
for i in range(M):
    a, b = map(int, input().split())
    key = 0
    for x in set(map(int, input().split())):
        key += 2 ** (x-1)
    op |= key
    if keys[key] > a:
        keys[key] = a

if op != 2**N - 1:
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(M)]
i, l = 0, 0
while keys[i] == 10000000:
    i += 1
dp[0][i] = keys[i]

while True:
    l += 1
    i += 1
    while keys[i] == 10000000:
        if i == 2**N:
            print(dp[l-1][-1])
            exit()
        i += 1

    v = keys[i]
    dp[l][i] = min(v, dp[l-1][i])
    for j in range(1, 2**N):
        if dp[l-1][j] != 10000000:
            if dp[l][i | j] == 10000000:
                dp[l][i | j] = min(dp[l-1][i | j] , dp[l-1][j] + v)
            else:
                dp[l][i | j] = min(dp[l][i | j], dp[l-1][j] + v)

            if dp[l][j] == 10000000:
               dp[l][j] = dp[l-1][j]

Submission status: Time Limit Exceeded

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

a = []
b = []
c = []

for i in range(M):
    temp1,temp2 = map(int,input().split())
    temp3 = list(map(int,input().split()))
    a.append(temp1)
    b.append(temp2)
    c.append(temp3)

INF = 10**8

dp = [INF]*(1<<N)
dp[0] = 0

for i in range(M):
    now = 0
    for j in range(b[i]):
        now |= 1<<(c[i][j]-1)
    for k in range(1<<N):
        dp[k|now] = min(dp[k|now],dp[k]+a[i])

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

print(dp[(1<<N)-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = 0, dict()
for i in range(M):
    a, b = map(int, input().split())
    key = 0
    for x in set(map(int, input().split())):
        key += 2 ** (x-1)
    op |= key
    if key not in keys.keys() or keys[key] > a:
        keys[key] = a

if op != 2**N - 1:
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keys))]
keyslist = list(keys.keys())
dp[0][keyslist[0]] = keys[keyslist[0]]
for i in range(1, len(keys)):
    k = keyslist[i]
    v = keys[k]
    dp[i][k] = min(v, dp[i-1][k])
    for j in range(1, 2**N):
        if dp[i-1][j] != 10000000:
            if dp[i][j | k] == 10000000:
                dp[i][j | k] = min(dp[i-1][j | k], dp[i-1][j] + v)
            else:
                dp[i][j | k] = min(dp[i][j | k], dp[i-1][j] + v)

            if dp[i][j] == 10000000:
               dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

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

INF = float('inf')
dp = [INF for j in range(2**n)]

dp[0] = 0

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

    k = 0
    for ci in c:
        ci -= 1
        k |= (1 << ci)
    for j in range(2**n):
        l = k | j
        dp[l] = min(dp[l], dp[j] + a)

if dp[2**n-1] == INF:
    print(-1)
else:
    print(dp[2**n-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def matdprint(mat):
    if debug == True:
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                print(mat[i][j], end=', ')
            print()

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7
def conv(s):
    cnt = 0
    for n in s:
        cnt += 2**n
    return cnt

def main():

    N, M = LI()

    a_list = []
    b_list = []
    c_list = []
    for i in range(M):
        a, b = LI()
        a_list.append(a)
        b_list.append(b)
        c_list.append(LI())

    dp = [[0 for j in range(2**N)]for i in range(M)]

    def conv(c):
        key = 0
        for i in c:
            key += 2**(i-1)
        return key

    def update(i, j, a):
        if dp[i][j] == 0:
            dp[i][j] = a
        else:
            dp[i][j] = min(dp[i][j], a)

    for i in range(M):
        c = c_list[i]
        a = a_list[i]
        key = conv(c)
        dprint('i', i, 'a', a, 'key', key)

        # 無に自分を入れるパターン
        if dp[i - 1][key] != 0:
            dp[i][key] = min(dp[i - 1][key], a)
        else:
            dp[i][key] = a


        for j in range(2**N):
            org_key = int(bin(j), 2)
            or_key = int(bin(j | key), 2)

            # 直前パターンに自分を足す場合
            if dp[i-1][org_key] == 0:
                # 直前orgがなければ足せない
                dprint('org_key', org_key, 'or_key', or_key, 'pass')
            else:
                # 直前がある場合、直前orgに足したのを入れる
                update(i, or_key, dp[i-1][org_key] + a)

                dprint('org_key', org_key, 'or_key', or_key, dp[i][or_key])

            # 直前パターンをすべて引き継がせる
            if dp[i-1][j] != 0:
                update(i, j, dp[i-1][j])

        matdprint(dp)

    matdprint(dp)
    ans = dp[M-1][(2**N)-1]
    if ans == 0:
        print(-1)
    else:
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = set(), dict()
for i in range(M):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    op |= c
    key = 0
    for x in c:
        key += 2 ** (x-1)
    if key not in keys.keys() or keys[key] > a:
        keys[key] = a

if op != set(range(1,N+1)):
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keys))]
keyslist = list(keys.keys())
dp[0][keyslist[0]] = keys[keyslist[0]]
for i in range(1, len(keys)):
    k = keyslist[i]
    v = keys[k]
    dp[i][k] = min(v, dp[i-1][k])
    for j in range(1, 2**N):
        if dp[i-1][j] != 10000000:
            dp[i][j | k] = min(dp[i][j | k], dp[i-1][j | k], dp[i-1][j] + v)
            if dp[i][j] == 10000000:
               dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = set(), dict()
for i in range(M):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    op |= c
    key = 0
    for x in c:
        key += 2 ** (x-1)
    if key not in keys.keys() or keys[key] > a:
        keys[key] = a

if op != set(range(1,N+1)):
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keys))]
keyslist = list(keys.keys())
dp[0][keyslist[0]] = keys[keyslist[0]]
for i in range(1, len(keys)):
    k = keyslist[i]
    v = keys[k]
    dp[i][k] = min(v, dp[i-1][k])
    for j in range(1, 2**N):
        if dp[i-1][j] != 10000000:
            dp[i][j | k] = min(dp[i][j | k], dp[i-1][j | k], dp[i-1][j] + v)
            dp[i][j] = min(dp[i][j], dp[i-1][j])

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
l=[]
for i in range(m):
  l2=[]
  a,b=map(int,input().split())
  l2.append(a)
  x=list(map(int,input().split()))
  ct=0
  for i in range(n):
    if i+1 in x:
      ct+=2**i
  l2.append(ct)
  l.append(l2)

dp=[[999999999999 for i in range(2**n)] for j in range(m+1)]
dp[0][0]=0
for i in range(1,m+1):
  for j in range(2**n):
    dp[i][j|l[i-1][1]]=min(dp[i-1][j|l[i-1][1]],dp[i-1][j]+l[i-1][0],dp[i][j|l[i-1][1]])
  for j in range(2**n):
    dp[i][j]=min(dp[i][j],dp[i-1][j])

if dp[m][2**n-1]<10**11:
  print(dp[m][2**n-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = set(), dict()
for i in range(M):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    op |= c
    key = 0
    for x in c:
        key += 2 ** (x-1)
    if key not in keys.keys() or keys[key] > a:
        keys[key] = a

if op != set(range(1,N+1)):
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keys))]
dp[0][list(keys.keys())[0]] = list(keys.values())[0]
for i in range(1, len(keys)):
    k = list(keys.keys())[i]
    v = keys[k]
    dp[i][k] = min(v, dp[i-1][k])
    check = set()
    for j in range(1, 2**N):
        if dp[i-1][j] != 10000000:
            check.add(j)
            dp[i][j | k] = min(dp[i][j | k], dp[i-1][j | k], dp[i-1][j] + v)
            dp[i][j] = min(dp[i][j], dp[i-1][j])

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = set(), dict()
for i in range(M):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    op |= c
    key = 0
    for x in c:
        key += 2 ** (x-1)
    if key not in keys.keys() or keys[key] > a:
        keys[key] = a

if op != set(range(1,N+1)):
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keys))]
k = list(keys.keys())[0]
dp[0][k] = keys[k]
check = set([k])
for i in range(1, len(keys)):
    k = list(keys.keys())[i]
    v = keys[k]
    dp[i][k] = min(v, dp[i-1][k])
    n_check = set([k])
    for j in check:
        if dp[i-1][j] != 10000000:
            check.add(j)
            dp[i][j | k] = min(dp[i][j | k], dp[i-1][j | k], dp[i-1][j] + v)
            dp[i][j] = min(dp[i][j], dp[i-1][j])
        n_check.add(j | k)
        n_check.add(j)
    check = set([]) | n_check

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
prices = []
keymap = []
for _ in range(m):
    a, b = map(int, input().split())
    prices.append(a)
    c = list(map(int, input().split()))
    state = 0
    for ck in c:
        state |= 1 << ck - 1
        # print(format(state, "b"))
    keymap.append(state)

# print(keymap)

dp = [float("inf")] * (1 << n)  # 2 ** n
dp[0] = 0

for price, keyto in zip(prices, keymap):
    # print("--- step start ---")
    # print(dp)
    dp_new = dp[:]
    for s, d in enumerate(dp):
        # print("=== DP ===")
        # print("s:", format(s, "b"))
        # print("c:", format(keyto, "b"))
        dp_new[s | keyto] = min(d + price, dp_new[s | keyto])

    dp = dp_new
    # print(dp)

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

Submission status: Time Limit Exceeded

Solution code:
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 = list(map(int, input().split()))

    key = 0

    for j in c:
        key += 2 ** (j-1)

    for j in range(2**N):
        dp[j | key] = min(dp[j | key], dp[j] + a)

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split());D=[0]+[9**9]*(1<<N)
for i in range(M):
 a,_=input().split();s=sum(1<<~-int(c)for c in input().split())
 for j in range(1<<N):D[s|j]=min(D[s|j],D[j]+int(a))
print(D[-2]%(9**9)or-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
op, keys = set(), dict()
for i in range(M):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    op |= c
    key = 0
    for x in c:
        key += 2 ** (x-1)
    if key not in keys.keys() or keys[key] > a:
        keys[key] = a

if op != set(range(1,N+1)):
    print(-1)
    exit()

dp = [[10000000 for _ in range(2**N)] for _ in range(len(keys))]
dp[0][list(keys.keys())[0]] = list(keys.values())[0]
for i in range(1, len(keys)):
    k = list(keys.keys())[i]
    v = keys[k]
    dp[i][k] = min(v, dp[i-1][k])
    check = set()
    for j in range(1, 2**N):
        if dp[i-1][j] != 10000000:
            check.add(j)
            dp[i][j | k] = min(dp[i][j | k], dp[i-1][j | k], dp[i-1][j] + v)

    for j in check:
        if dp[i][j] == 10000000:
            dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** N)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if i > 2 ** N:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i | cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp][j] = less(dp[i][j - 1] + ab[j][0], dp[temp][j])
    dp[i][j] = less(dp[i][j], dp[i][j - 1])
    dp[cc[j]][j] = less(ab[j][0], dp[cc[j]][j])
    Q.append((temp, j + 1))
    Q.append((i, j + 1))
    Q.append((cc[j], j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp][j] = less(ab[j][0], dp[temp][j])
    Q.append((temp, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split());D=[0]+[9e9]*(1<<N)
for i in range(M):
 a,_=input().split();s=sum(1<<~-int(c)for c in input().split())
 for j in range(1<<N):t=s|j;D[t]=min(D[t],D[j]+int(a))
print(-1*(D[-2]>8e9)or D[-2])

Submission status: Time Limit Exceeded

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

class Key:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

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

def solve(i, j):
    if dp[i][j] != inf:
        return dp[i][j]
    else:
        remain = j
        for c in keys[i].c:
            remain = remain & ~(1 << (c-1))

        if i > 0:
            dp[i][j] = min(solve(i-1, remain) + keys[i].a, solve(i-1, j))
        elif remain == 0:
            dp[i][j] = min(keys[i].a, dp[i][j])

        return dp[i][j]


dp = [[inf for i in range(2**n)] for j in range(m)]
for i in range(m):
    dp[i][0] = 0

for i in range(m):
    for j in range(1, 2**n):
        ans = solve(i, j)

ans = solve(m-1, 2**n-1)
if ans == inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

n, m = map(int, input().split())
keys = []
for i in range(m):
    a, b = map(int, input().split())
    cs = reduce(lambda x, y: x | y, ((1 << (int(s) - 1)) for s in input().split()))
    keys.append((a, cs))

pow_n = 1 << n

table = [None] * (m + 1)
for i in range(m + 1):
    table[i] = [float('inf')] * pow_n

table[0][0] = 0
for i in range(m):
    for j in range(pow_n):
        table[i + 1][j] = min(table[i + 1][j], table[i][j])
        index = j | keys[i][1]
        table[i + 1][index] = min(table[i + 1][index], table[i][j] + keys[i][0])

print(table[m][pow_n - 1] if table[m][pow_n - 1] < float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque as dq
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = min(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = min(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split());D=[0]+[9e9]*(1<<N)
for i in range(M):
 a,_=input().split();s=sum(2**~-int(c)for c in input().split())
 for j in range(1<<N):t=s|j;D[t]=min(D[t],D[j]+int(a))
print(-1*(D[-2]>8e9)or D[-2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque as dq
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i ^ 0
  temp2 = 0
  for k in range(ab[j][1]):
    t = 2 ** (c[j][k] - 1)
    temp2 = temp2 | t
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = min(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = min(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque as dq
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
#print(ab, c)
Q = dq([])
Q.append((0, 0))
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  temp = i ^ 0
  temp2 = 0
  for k in range(ab[j][1]):
    t = 2 ** (c[j][k] - 1)
    temp2 = temp2 | t
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = min(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = min(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])

Submission status: Time Limit Exceeded

Solution code:
import copy
def search_ans(fee,box,not_open_luxuary,feebox):
  for k,i in enumerate(box):
    if list(set(i[1]) & set(not_open_luxuary))!=[]:
      a=copy.deepcopy(not_open_luxuary)
      t=copy.deepcopy(box)
      fee1=fee
      for j in list(set(i[1]) & set(a)):
        a.remove(j)
      fee1+=i[0]
      if a==[]:
        feebox.append(fee1)
      else:
        t.pop(k)
        search_ans(fee1,t,a,feebox)
	
def main():
  n,m=map(int,input().split())
  index_box=list(range(n+1))
  index_box.pop(0)
  box=[]
  N=[0]*13
  N[0]=10**4
  feebox=[]
  M=[]
  for i in range(m):
  	a1,b1=map(int,input().split())
  	c1=list(map(int,input().split()))
  	box.append([a1,c1])
  search_ans(0,box,index_box,feebox)
  if feebox==[]:
    print(-1)
  else:
    print(min(feebox))

main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split());D=[9e9for _ in range(2**N)];D[0]=0
for i in range(M):
 a,_=input().split();s=sum(2**~-int(c)for c in input().split())
 for j in range(2**N):t=s|j;D[t]=min(D[t],D[j]+int(a))
print(-1*(D[-1]>8e9)or D[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split());D=[9**9for _ in range(2**N)];D[0]=0
for i in range(M):
 a,_=input().split();s=sum(2**~-int(c)for c in input().split())
 for j in range(2**N):D[s|j]=min(D[s|j],D[j]+int(a))
print(-1*(D[-1]>8**9)or D[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split());D=[9e9for _ in range(2**N)];D[0]=0
for i in range(M):
 a,_=input().split();s=sum(2**~-int(c)for c in input().split())
 for j in range(2**N):D[s|j]=min(D[s|j],D[j]+int(a))
print(-1*(D[-1]>8e9)or D[-1])

Submission status: Time Limit Exceeded

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

aa = []
aaa = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, readline().split()))
    c = list(map(int, readline().split()))
    aa.append(a)
    for j in range(b):
        aaa[c[j]-1].append(i)

# print(aaa)

pats = []
def dfs(arr,depth):
    if depth == N:
        return pats.append(arr)
    for i in range(len(aaa[depth])):
        tmp = aaa[depth][i]
        dfs(arr + [tmp], depth + 1)

dfs([], 0)
# print(pats)
ans = -1
for i in range(len(pats)):
    if len(pats[i]) == N:
        if ans == -1:
            ans = (10**5)*12
        s = 0
        idx = set(pats[i])
        for j in idx:
            s += aa[j]
        ans = min(s, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A = [0]*M
C = []
D = [[] for _ in range(N)]
for i in range(M):
    A[i], _ = map(int,input().split())
    C.append([x - 1 for x in map(int,input().split())])
    for j in C[i]:
        D[j].append(i)

def trial(remain_box_lists):
    min_keys = N
    min_key_box = remain_box_lists[0]
    for d in remain_box_lists:
        l = len(D[d])
        if not l: return -1
        elif l < min_keys:
            min_keys = l
            min_key_box = d
    min_cost = 10e5
    for key in D[d]:
        rem = [r for r in remain_box_lists if r not in C[key]]
        if len(rem) == 0:
            if A[key] < min_cost:
                min_cost = A[key]
        else:
            cost = trial(rem)
            if cost == -1: return -1
            if (cost+ A[key]) < min_cost:
                min_cost = cost + A[key]
    return min_cost
print(trial(list(range(N))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = map(int,input().split())
a=[0 for _ in range(M)]
b=[0 for _ in range(M)]
dict = {}
for i in range(M):
    a[i],b[i] = map(int,input().split())
    l = list(map(int,input().split()))
    C = np.array(l)
    v = 0
    for x in l:
        v += 2**x
    if(v not in dict):dict[v] = a[i]
    else:dict[v] = min(dict[v],a[i])
    
k = dict.keys()
k = sorted(list(k))
val = [dict[k1] for k1 in k]

maxx = 0
xs = set([0])
for i in range(1,N+1):
    xt = list(xs)
    for x in xt:
        xs.add(x|2**(i))
for i in range(N):
    maxx += 2**(i+1)
# print(xs)
#exit()
inf = max(a) * M
dp = [[inf for _ in range(maxx+1)] for _ in range(len(k)+1)]
dp[0][0] = 0
# print(val)
# print(k)

for i in range(len(k)):
    for x in xs:
        dp[i+1][x] = min([dp[i+1][x],dp[i][x]])
        # print(i+1,x,x|k[i],dp[i+1][x|k[i]],dp[i][x]+val[i])
        dp[i+1][x|k[i]] = min([dp[i+1][x|k[i]],dp[i][x]+val[i]])
        
if(dp[-1][-1] == inf):print(-1)
else:print(dp[-1][-1])

#for i in range(M):print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = map(int,input().split())
a=[0 for _ in range(M)]
b=[0 for _ in range(M)]
dict = {}
for i in range(M):
    a[i],b[i] = map(int,input().split())
    l = list(map(int,input().split()))
    C = np.array(l)
    v = 0
    for x in l:
        v += 2**x
    if(v not in dict):dict[v] = a[i]
    else:dict[v] = min(dict[v],a[i])
    
k = dict.keys()
k = sorted(list(k))
val = [dict[k1] for k1 in k]

maxx = 0
xs = set([0])
for i in range(1,N+1):
    xt = list(xs)
    for x in xt:
        xs.add(x|2**(i))
for i in range(N):
    maxx += 2**(i+1)
# print(xs)
#exit()
inf = 100000000
dp = [[inf for _ in range(maxx+1)] for _ in range(len(k)+1)]
dp[0][0] = 0
# print(val)
# print(k)

for i in range(len(k)):
    for x in xs:
        dp[i+1][x] = min([dp[i+1][x],dp[i][x]])
        # print(i+1,x,x|k[i],dp[i+1][x|k[i]],dp[i][x]+val[i])
        dp[i+1][x|k[i]] = min([dp[i+1][x|k[i]],dp[i][x]+val[i]])
        
if(dp[-1][-1] == inf):print(-1)
else:print(dp[-1][-1])

#for i in range(M):print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = map(int,input().split())
a=[0 for _ in range(M)]
b=[0 for _ in range(M)]
c = np.zeros((M,N))
c=np.array([[False for _ in range(N)] for _ in range(M)])

dict = {}
for i in range(M):
    a[i],b[i] = map(int,input().split())
    l = list(map(int,input().split()))
    C = np.array(l)
    v = 0
    for x in l:
        v += 2**x
    if(v not in dict):dict[v] = a[i]
    else:dict[v] = min(dict[v],a[i])
    c[i,C-1] = True
    
k = dict.keys()
k = sorted(list(k))
val = [dict[k1] for k1 in k]

maxx = 0
xs = set([0])
for i in range(1,N+1):
    xt = list(xs)
    for x in xt:
        xs.add(x|2**(i))
for i in range(N):
    maxx += 2**(i+1)
# print(xs)
#exit()
inf = 100000000
dp = [[inf for _ in range(maxx+1)] for _ in range(len(k)+1)]
dp[0][0] = 0
# print(val)
# print(k)

for i in range(len(k)):
    for x in xs:
        dp[i+1][x] = min([dp[i+1][x],dp[i][x]])
        # print(i+1,x,x|k[i],dp[i+1][x|k[i]],dp[i][x]+val[i])
        dp[i+1][x|k[i]] = min([dp[i+1][x|k[i]],dp[i][x]+val[i]])
        
if(dp[-1][-1] == inf):print(-1)
else:print(dp[-1][-1])

#for i in range(M):print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
INF = 10 ** 12
T = [2**i for i in range(N)]
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    base = sum(T[c-1] for c in C)
    for j in range(2**N):
        if any(not ((j >> (c-1)) & 1) for c in C):
            step = base - sum(T[c-1] for c in C if ((j >> (c-1)) & 1))
            dp[j+step] = min(dp[j+step], dp[j]+a)

print(dp[-1] if dp[-1] < INF else -1)