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: Accepted

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N, M = iip(False)

    dp = {"0"*N:0}
    keys = []
    for i in range(M):
        a, b = iip(True)
        c = iip(True)
        keys.append((a, c))

    for cost, boxes in keys:
        for k, v in list(dp.items()):
            k_add = list(k)
            for box in boxes:
                #print(k_add)
                k_add[int(box) - 1] = "1"
            v = v + cost
            k_add = "".join(k_add)
            if k_add not in dp:
                dp[k_add] = v
            else:
                dp[k_add] = min(v, dp[k_add])

        #print(cost)
        #print(boxes)

    #print(dp)
    keyans = "1" * N
    if keyans not in dp:
        return -1
    else:
        return dp[keyans]


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = []
c = []
for i in range(m):
    ab.append(list(map(int,input().split())))
    s = 0
    for j in map(int,input().split()):
        s += 2**(j-1)
        
    c.append(s)

dp = [[float("INF")]*(2**n) for i in range(m+1)]

dp[0][0] = 0

for i in range(m):
    for j in range(2**n):
        if dp[i][j] != float("INF"):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            x = j|c[i]
            dp[i+1][x] = min(dp[i+1][x],dp[i][j]+ab[i][0])

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = []
key = []
for i in range(m):
    d = [10**15]*(2**n)
    d[0] = 0
    dp.append(d)
for i in range(m):
    cost,num = map(int,input().split())
    if num == 1:
        t = int(input())
        key.append([cost,2**(t-1)])
    else:
        p = list(map(int,input().split()))
        cur = 0
        for i in range(len(p)):
            cur += 2**(p[i]-1)
        key.append([cost,cur])
for i in range(m):
    for j in range(2**n):
        if i != 0:
            dp[i][j] = min(dp[i][j],dp[i-1][j])
        dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0])
if dp[m-1][2**n-1] != 10**15:
    print(dp[m-1][2**n-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import sys

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def main():
    N, M = map(int, input().split())
    keys = []
    for _ in range(M):
        a, b = map(int, input().split())
        bits = sum([1 << (i - 1) for i in map(int, input().split())])
        keys.append([a, bits])

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [None]*m
c = [0]*m
for i in range(m):
    a[i], b = map(int, input().split())
    ls = list(map(int,input().split()))
    for j in ls:
        c[i] |= 1<<(j-1)
n2 = 1<<n
dp = [1e9]*(n2)
dp[0] = 0
for i in range(m):
    for S in range(n2):
        if dp[S|c[i]] > dp[S]+a[i]:
            dp[S|c[i]] = dp[S]+a[i]
if dp[(n2)-1] < 1e9:
    print(dp[(n2)-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dfs, dp, bit全探索
# 箱が12個以下
N, M = lr()
keys = [None] * M
for i in range(M):
    a, b = lr()
    C = lr()
    bit = 0
    for c in C:
        bit += 1 << (c-1)
    keys[i] = (a, bit)

INF = 10 ** 9
dp = [INF] * 2 ** N # 2**N - 1 が全ての箱を開けられる状態の最小値
dp[0] = 0
for key in keys:
    a, bit = key
    for i in range(2 ** N):
        dp[i|bit] = min(dp[i|bit], dp[i] + a)

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
key=[]
cost=[]
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)
    cost.append(a)

node=2**N

dp=[[10**10 for i in range(0,node)] for j in range(0,M)]

for i in range(0,M):
    dp[i][node-1]=0
#i:何番までか j:手に入れた鍵
for i in range(0,M):
    for j in range(1,node):
        k=node-1-j
        if i==0:
            if k|key[0]==node-1:
                dp[0][k]=cost[0]
        else:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k|key[i]]+cost[i])

if dp[M-1][0]>=10**10:
    print(-1)
else:
    print(dp[M-1][0])

Submission status: Accepted

Solution code:
INF = 10**9
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))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        if d < tmp[j]:
            tmp[j] = d
        if d+a < tmp[j|c]:
            tmp[j|c] = d+a
    dp = tmp

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

Submission status: Accepted

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 | j] > dp[j] + a:
            dp[c | j] = dp[j] + a

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

Submission status: Accepted

Solution code:


def main():
    n,m=map(int,input().split())

    L=2**n

    cost=[0]+[10**8 for i in range(L-1)]

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

        c = sum(map(lambda x:2**(int(x)-1), input().split()))
        for i in range(L):
            q = c|i
            cost[q] = min(cost[q], cost[i]+a)
    print(cost[L-1] if cost[L-1]<10**8 else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
key = [0] * M
cost = [0] * M
for i in range(M):
    a, b = map(int,input().split())
    cost[i] = a
    key_id = list(map(int,input().split()))
    for j in range(b):
        key[i] |= (1 << (key_id[j] - 1))
dp = [[float("inf")] * (1<<N)] * (M + 1)
dp[0][0] = 0
for i in range(M):
    for j in range(1<<N):
        if dp[i + 1][j | key[i]] > dp[i][j] + cost[i]:
            dp[i + 1][j | key[i]] = dp[i][j] + cost[i]
        if dp[i + 1][j] > dp[i][j]:
            dp[i + 1][j] = dp[i][j]
if dp[-1][-1] == float("inf"):
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Accepted

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]

    dp[i%2][mask] = min(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: Accepted

Solution code:
n,m = map(int, input().split())
a=[]
c=[]
for i in range(m):
    tmp,_=map(int, input().split())
    a.append(tmp)
    tmp=list(map(int, input().split()))
    bit = 0
    for b in tmp:
        bit+=(1<<(b-1))
    c.append(bit)

dp = [[10**9 for i in range(2**n)] for j in range(m+1)]
dp[0][0]=0

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

ans=dp[-1][-1]
if ans ==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
for i in range(m):
  a,b = map(int,input().split())
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)

Submission status: Accepted

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)]
for i in range(m + 1):
    dp[i][0] = 0

for i in range(1, m + 1):
    a, c_ = items[i - 1]
    # 鍵を使わない
    for j in range(2**n):
        dp[i][j] = dp[i - 1][j]
    # 鍵を使うときと使わないときの比較
    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: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    L=2**n
    cost=[0]+[10**8 for i in range(L-1)]

    for _ in range(m):
        a,_=map(int,input().split())
        c=sum([2**(int(i)-1) for i in input().split()])
        for j in range(L):
            q=j|c
            x=cost[j]+a
            if cost[q]>x:
                cost[q]=x
    print(cost[L-1] if cost[L-1]<10**8 else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
L=2**n
cost=[0]+[10**8 for i in range(L-1)]

for i in range(m):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for j in range(L):
        q=j|c
        x=cost[j]+a
        if cost[q]>x:
            cost[q]=x
print(cost[L-1] if cost[L-1]<10**8 else -1)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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 input(): return sys.stdin.readline().strip()
def INT(): return int(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()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
def main():
    N, M = MAP()
    dp = [INF] * (1<<N)
    dp[0] = 0

    for i in range(M):
        a, b = MAP()
        c = LIST()
        d = 0
        # 1を立てる
        for x in c:
            # 1が存在するなら，dの一番最後，右から0番目，0シフト目に必要
            d += 1<<(x-1)
        for j in range(1<<N): # 2 ** N 列見る
    #         # テーブルは一列ずつ見て更新しよう
            tmp = j|d
            dp[tmp] = min(dp[tmp], dp[j] + a)
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

N, M = map(int, input().split())
INF = float('inf')
dp = [INF] * (1 << N)
dp[0] = 0
for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for i in c:
        bit += 1 << (i-1)
    for i in range(1 << N):
        dp[i | bit] = min(dp[i | bit], dp[i] + a)
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Accepted

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

INF = 100000000
dp = [[INF] * 2**N for _ in range(M + 1)]
dp[0][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in range(2**N):
        pre_bit = next_bit = bit
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in range(2**N):
        pre_bit = bit
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
cos = [0] * M
bit = [0] * M
for i in range(M):
    a, b = (int(j) for j in input().split())
    cos[i] = a
    c = [int(j) for j in input().split()]
    bit[i] = sum([2 ** (j-1) for j in c])

DP = [[float("inf")] * 2**N for counter1 in range(M+1)]
for i in range(M):
    DP[i][0] = 0

for i in range(M):
    a = cos[i]
    bi = bit[i]
    for j in range(2**N):
        DP[i+1][j|bi] = min(DP[i+1][j|bi], DP[i][j] + a)
        DP[i+1][j] = min(DP[i+1][j], DP[i][j])

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
digit = ''.join(['0',str(n),'b'])
cost = [0] + [m*10**5+1] * (2**n-1)
for i in range(m):
  a, b = map(int,input().split())
  c = list(map(int, input().split()))
  cc = 0
  for j in c:
      cc += 2**(j-1)
  for j in range(2**n):
    jj = j | cc
    cost[jj] = min(cost[jj],cost[j]+a)
if cost[-1] == m*10**5+1:
  print(-1)
else:
  print(cost[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
for i in range(m):
  a,b = map(int,input().split())
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    if dp[j|s] > dp[j]+a:
      dp[j|s] = dp[j]+a
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
for i in range(m):
  a,b = map(int,input().split())
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    keys = [[None for j in range(2)] for i in range(m)]
    for i in range(m):
        a, b = map(int, input().split())
        keys[i][0] = a
        keys[i][1] = 0
        c = list(map(int, input().split()))
        for j in c:
            keys[i][1] += int(pow(2, j-1))
    dp = [10**9 for i in range(int(pow(2, n)))]
    dp[0] = 0
    for i in range(int(pow(2, n))):
        for j in range(m):
            if dp[i | keys[j][1]] > dp[i] + keys[j][0]:
                dp[i | keys[j][1]] = dp[i] + keys[j][0]
    if dp[int(pow(2, n)) - 1] == 10**9:
        print("-1")
    else:
        print(dp[int(pow(2, n)) - 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = []
    for i in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        s = 0
        for c in C:
            c -= 1
            s |= (1 << c)
        S.append((a,s))

    dp = [float('inf')] * (1 << N)
    dp[0] = 0
    for i in range(1 << N):
        for j in range(M):
            t = i | S[j][1]
            dp[t] = min(dp[t], dp[i] + S[j][0])

    if dp[(1<<N)-1] == float('inf'):
        print(-1)
    else:
        print(dp[(1<<N)-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
### 提出 #10098255

##頭良すぎて草

##x | y    x と y のビット単位 論理和
##x ^ y    x と y のビット単位 排他的論理和
##x & y    x と y のビット単位 論理積
##x << n   x の n ビット左シフト
##x >> n   x の n ビット右シフト
##~x       x のビット反転

n,m=map(int,input().split())
p=2**n
inf=10**9
dp=[inf]*p
dp[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=sum([2**(j-1) for j in list(map(int,input().split()))])
    for k in range(p):
        if dp[k|c]>dp[k]+a:
            dp[k|c]=dp[k]+a
print(dp[-1] if dp[-1]!=inf else -1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=2**n
inf=10**9
dp=[inf]*p
dp[0]=0
for i in range(m):
  a,b=map(int,input().split())
  c=sum([2**(j-1) for j in list(map(int,input().split()))])
  for k in range(p):
    if dp[k|c]>dp[k]+a:
      dp[k|c]=dp[k]+a
print(dp[-1] if dp[-1]!=inf else -1)

Submission status: Accepted

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

for _ in range(m):
    cost, types = map(int, input().split())
    to_open = list(map(int, input().split()))
    keys.append([cost, to_open])

DP = [10**9] * (2 ** n)
DP[0] = 0

for cost, (to_open) in keys:
    openable = 0
    for open in to_open:
        openable |= 1 << (open-1)

    for i in range(2 ** n):
        pattern = i | openable
        DP[pattern] = min(DP[pattern], DP[i] + cost)

ans = DP[2**n - 1]

if ans == 10 ** 9:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = min(a,dp[m])
dp[0] = 0
for i in range(1<<N):
  for j in range(1<<N):
    dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = a
dp[0] = 0
for i in range(M):
  for j in range(1<<N):
    a,m = ls[i]
    dp[m|j] = min(dp[m|j], a+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
bit_cnt = 2 ** N # 箱は最大で12個
INF = 10 ** 10
dp = [INF] * bit_cnt
dp[0] = 0
for _ in range(M):
    price, b = lr()
    open = sum([2 ** (x-1) for x in lr()]) # 1と3の箱を開ける鍵なら101となる
    for j in range(bit_cnt):
        if dp[j|open] > dp[j] + price:
            dp[j|open] = dp[j] + price

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
# 解き直し08

Submission status: Accepted

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


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    K = []
    for _ in range(M):
        a, _ = read_values()
        T = read_list()
        K.append((a, T))

    dp = [10 ** 8] * (2 ** N + 10)
    dp[0] = 0
    for a, T in K:
        k = 0
        for t in T:
            k += 1 << (t - 1)
        for i in range(2 ** N):
            dp[i | k] = min(dp[i | k], dp[i] + a) 

    res = dp[2 ** N - 1]
    print(res if res != 10 ** 8 else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 15:20-

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

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

pattern = {0}

for i in range(1, m+1):
  ai, bi = map(int, input().split()) 
  ci_bit = sum(2 ** (cij - 1) for cij in map(int, input().split()))
  new_pattern = set()
  for j in pattern:
    dp[i][j | ci_bit] = min(dp[i][j | ci_bit], dp[i-1][j] + ai)
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    new_pattern.add(j | ci_bit)
  pattern |= new_pattern


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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(list(map(int, input().split())))
    C.append(list(map(int, input().split())))

INF = 10 ** 9 + 7
dp = [INF] * (2 ** N)
dp[0] = 0

for i, ((a, b), c) in enumerate(zip(AB, C)):
    num = int("".join(["01"[int(i + 1 in c)] for i in range(N)]), 2)
    for j in range(2 ** N):
        dp[j | num] = min(dp[j | num], dp[j] + a)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M = MI()
	dp = [float("inf")] * (2**N)
	dp[0] = 0
	for _ in range(M):
		a,b = MI()
		cc = LI()
		state = 0
		for c in cc:
			c -= 1
			state += (1 << c)
		for i in range(2**N):
			if(dp[i]!=float("inf")):
				dp[i|state] = min(dp[i|state], dp[i]+a)
	if(dp[-1]!=float("inf")):
		print(dp[-1])
	else:
		print(-1)


main()

Submission status: Accepted

Solution code:
from bisect import *
N,M=map(int,input().split())
kagi=[]
for i in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    value=0
    for i in range(b):
        C[i]-=1
        value+=2**C[i]

    kagi.append([a,value])


dp=[[10**8 for i in range(2**N)] for m in range(M+1)]
dp[0][0]=0
for i in range(M):
    for s in range(2**N):
        dp[i+1][s]=min(dp[i][s],dp[i+1][s])
        dp[i+1][s|kagi[i][1]]=min(dp[i+1][s|kagi[i][1]],dp[i][s]+kagi[i][0])
if 10**8==dp[M][-1]:
    print(-1)
else:
    print(dp[M][-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[0]*M
import heapq
import collections
from itertools import permutations
table=collections.defaultdict(list)
AC=[[0,0] for i in range(M)]
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  AC[i][0]=a
  tmp=set(map(int,input().split()))
  for x in tmp:
    AC[i][1] |= 1<<(x-1)
dp=[10**9]*(2**N)
dp[0]=0

for i in range(1,2**N):
  k=0
  s=set()
  for j in range(1,i):
    if i & j == j:
      dp[i]=min(dp[i],dp[j]+dp[i^j])
  for a,c in AC:
    if c&i == i:
      dp[i]=min(dp[i],a)
  #print(dp[i],bin(i))
  
if dp[-1]==10**9:
  print(-1)
else:
  print(dp[-1])
#print(dp)

  
  
#print(AC)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    *c, = map(int, input().split())
    l.append((a, c))

inf = 10**12
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for cost, j in l:
        v = sum(map(lambda x:2**(x-1), j))
        dp[i|v] = min(dp[i|v], dp[i]+cost)

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

Submission status: Accepted

Solution code:
def main():
    N, M  = map(int, input().split())
    l = []
    for i in range(M):
        a, b = map(int, input().split())
        c = map(int, input().split())
        k = sum(2 ** (i-1) for i in c)
        l.append((a, k))
    m = [float('inf')] * (2 ** N)
    m[0] = 0
    for i in range(M):
        for j in range(2 ** N):
            m[j | l[i][1]] = min(m[j | l[i][1]], m[j] + l[i][0])
    if m[-1] == float('inf'):
        print('-1')
    else:
        print(m[-1])
main()

Submission status: Accepted

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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)

Submission status: Accepted

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

keys = []
for i in range(m):
  a,b = map(int,input().split())
  cs = list(map(int,input().split()))
  key = 0
  for c in cs:
    key += 2 **(c-1)
  dp[key] = a
  keys.append((key,a))
keys.sort()


for i in range(2**n):
  for key,a in keys:
    if dp[i|key] > dp[i] + a:
      dp[i|key] = dp[i] + a
print(dp[-1] if dp[-1] != float('inf') else -1)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
key = []
tmp = 0
for i in range(m):
    a,b = map(int, input().split())
    c = 0
    for i in map(int, input().split()):
        c += 1<<(i-1)
    key.append((a,c))
    tmp |= c
   
inf = float('INF')
flag = False
opened = 2**n
if tmp != opened -1:
    print(-1)
    exit()
dp = [inf for i in range(opened)]
dp[0] = 0
for a,c in key:
    for i in range(opened):
        if dp[i] + a < dp[i | c]:
            dp[i | c] = dp[i] + a

print(dp[opened-1] if dp[opened-1] else -1)
# print(dp)

Submission status: Accepted

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

cost = [0] * m
keys = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    cost[i] = a
    k = list(map(int, input().split()))
    for j in range(b):
        keys[i] |=  (1 << (k[j]-1))

INF = 10 ** 9 + 1
dp = [INF] * (2**n)
dp[0] = 0

for i in range(1 << n):
    if dp[i] == INF:
        continue
    for next_cost, next_key in zip(cost, keys):
        m = next_key | i
        dp[m] = min(dp[m], dp[i] + next_cost)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
INF = 10 ** 7
dp = [INF] * (2 ** N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    k = sum([2 ** (i - 1) for i in map(int, input().split())])
    for j in range(2 ** N):
        dp[j | k] = min(dp[j | k], dp[j] + a)

ans = dp[2 ** N - 1] if dp[2 ** N - 1] < INF else -1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
for i in range(M):
    a, b = map(int, input().split())
    C = map(int, input().split())
    A[i] = a
    K[i] = sum([2 ** (i - 1) for i in C])


INF = (1 << 32) - 1
dp = [[INF] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    for j in range(2 ** N):
        here = dp[i][j]
        dp[i + 1][j] = min(dp[i + 1][j], here)
        dp[i + 1][j | k] = min(dp[i + 1][j | k], dp[i][j | k], here + a)

ans = dp[M][2 ** N - 1] if dp[M][2 ** N - 1] < INF else -1
print(ans)

Submission status: Accepted

Solution code:
import sys
INF = sys.maxsize
N,M = map(int,input().split(" "))
tmp = []
for _ in range(M):
    a,b = map(int,input().split(" "))
    bit = 0
    nums = map(int,input().split(" "))
    for n in nums:
        bit += 2**(n-1)
    tmp.append((a,bit))

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

for i in range(M):
    a,bit = tmp[i]
    for j in range(2**N):
        cover = bit | j
        dp[cover] = min(dp[cover], dp[j] + a)

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

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    INF = 10**7
    k = []
    for _ in range(M):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        bit = 0
        for i in c:
            bit += 2**(i-1)
        k.append((a,bit))
    dp = [INF for _ in range(1<<N)]
    dp[0] = 0
    for i in range(M):
        a,bit = k[i]
        for j in range(1<<N):
            af = bit|j
            dp[af] = min(dp[af],dp[j]+a)
            
    print(dp[-1] if dp[-1] != INF else -1)
if __name__ == "__main__":
    main()