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

Solution (Python):

"""
宝箱の制約が12個なので、これの状態を集合とする.
全ての状態について、(これはdpテーブルの状態ではない)
全ての鍵について考え、
この2つの状態のorで得られる状態sのdpテーブルをcost最小値で更新
そのようにして得られるdp[-1]が答えで、
この時O(2^N*M)がだいたい60**6なのでギリok
"""
import sys
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
INF = 10**10
cost_len_key = []
for i in range(m):
    a,b = map(int,readline().split())
    lst1 = list(map(int,readline().split()))
    res = 0
    for j in lst1:
        res += 1<<(j-1)
    cost_len_key.append([a,b,res])


dp = [INF for _ in range(1<<n)]
dp[0] = 0 

for i in range(1<<n): 
    for j in cost_len_key: 
        s = i|j[2] 
        dp[s] = min(dp[s],dp[i]+j[0]) 

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

Solution (Python):

"""
宝箱の制約が12個なので、これの状態を集合とする.
鍵をcost昇順に並べる。
ある鍵について、新たに埋められる場所が存在するなら、その鍵を使ってみる
"""
import sys
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
INF = 10**10
cost_len_key = []
for i in range(m):
    a,b = map(int,readline().split())
    lst1 = list(map(int,readline().split()))
    res = 0
    for j in lst1:
        res += 1<<(j-1)
    cost_len_key.append([a,INF-b,res])

cost_len_key.sort()


dp = [INF for _ in range(1<<n)]
dp[0] = 0

for i in range(1<<n):
    for j in cost_len_key:
        s = i|j[2]
        dp[s] = min(dp[s],dp[i]+j[0])

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

Solution (Python):
import sys
import itertools

N,M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(map(int, input().split())))
    C.append(sum(1<<(int(x)-1) for x in map(int, input().split())))

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

for n,((a,b),c) in itertools.product(range(1<<N), zip(AB,C)):
    m = n|c
    x = dp[n] + a
    if dp[m] > x:
        dp[m] = x

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

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

Solution (Python):
N, M = map(int, input().split())
K = []

for _ in range(M):
    a, _ = map(int, input().split())
    k = 0
    for i in map(lambda a: int(a) - 1, input().split()):
        k |= (1 << i)
    K.append((a, k))

dp = [10**18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
    for a, k in K:
        if dp[state | k] > dp[state] + a:
            dp[state | k] = dp[state] + a
ans = dp[(1 << N) - 1]
print(ans if ans < 10**18 else -1)

Solution (Python):
n, m = map(int, input().split())
A = [0]*m
C = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    c = list(map(int, input().split()))
    c = [x-1 for x in c]
    C[i] = c


dp = [10**18]*(2**n)
dp[0] = 0
C_bit = [0]*m
for i in range(m):
    C_bit[i] = 0
    for j in C[i]:
        C_bit[i] += 2**j

for i in range(2**n):
    for j in range(m):
        ni = i | C_bit[j]
        dp[ni] = min(dp[ni], dp[i]+A[j])

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

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

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    A,B,C=[],[],[]
    for _ in range(M):
        a,b=map(int, input().split())
        A.append(a)
        B.append(b-1)
        C.append(list(map(lambda x:int(x)-1, input().split())))

    
    dp = [[10**9] * (1<<N) for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        ni = i + 1
        nj = 0
        for c in C[i]: nj |= 1 << c
        for j in range(1<<N):
            dp[ni][j] = min(dp[ni][j], dp[i][j])
            dp[ni][j|nj] = min(dp[ni][j|nj], dp[i][j] + A[i])

    print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] < 10**9 else -1)

if __name__ == '__main__':
    main()

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


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

Solution (Python):
n, m = map(int, input().split())
valists = [10**9 for _ in range(1<<n)]
valists[0] = 0
for i in range(m):
	values, b = map(int, input().split())
	c = list(map(int, input().split()))
	cnt = 0
	for j in range(b):
		cnt += 2**(c[j]-1)
	for j in range(len(valists)):
		x = j|cnt
		valists[x] = min(valists[x], valists[j]+values)
		


ans = valists[2**n-1]
if ans != 10**9:
	print(ans)
else:
	print(-1)

Solution (Python):
n, m = map(int, input().split())
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0
keys = []

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

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

Solution (Python):
N,M = map(int,input().split())
AB, C = [], []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18



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


dp[0] = 0

for i in range(1<<N):
    for (a, _), c in zip(AB,C):
        
        state = i | c
        dp[state] = min(dp[state], dp[i] + a)

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

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    A,B,C=[],[],[]
    for _ in range(M):
        a,b=map(int, input().split())
        A.append(a)
        B.append(b-1)
        C.append(list(map(lambda x:int(x)-1, input().split())))

    
    dp = [[10**9] * (1<<N) for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        ni = i + 1
        for j in range(1<<N):
            dp[ni][j] = min(dp[ni][j], dp[i][j])
            nj = j
            for c in C[i]: nj |= 1 << c
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + A[i])

    print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] < 10**9 else -1)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
a = []
b = []
c = []

MY_INF = 1000000007

for _ in range(M):
    a_tmp, b_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)
    c.append(list(map(int, input().split())))

c_bin = []
for i in range(M):
    c_bin.append(sum([1 << (cij - 1) for cij in c[i]]))
    
memo = [None] * (1 << N)

def dp(state):
    global MY_INF
    if state == (1 << N) - 1: return 0
    if memo[state] != None: return memo[state]
    
    rets = [MY_INF]
    for i in range(M):
        if (state | c_bin[i]) > state:
            rets.append(a[i] + dp((state | c_bin[i])))
    ret = min(rets)
    
    memo[state] = ret
    return ret

ans = dp(0)
if ans != MY_INF:
    print(ans)
else:
    print(-1)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Dist = [10 ** 20] * pow(2, N)
    Dist[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        C = [int(c) for c in input().split()]
        binaryC = 0
        for c in C: binaryC += pow(2, c-1)
        for j, d in enumerate(Dist):
            if d < 10 ** 20: Dist[j | binaryC] = min(Dist[j | binaryC], Dist[j] + a)
    print(Dist[-1] if Dist[-1] < 10 ** 20 else -1)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC142_E()

"""

"""

Solution (Python):
N,M = map(int,input().split())
from collections import defaultdict
INF = float('inf')
dic = defaultdict(lambda: INF)
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    d = 0
    for k in c:
        d |= (1<<(k-1))
    dic[d] = min(dic[d], a)

dp = [INF] * (1<<N)
dp[0] = 0
for k,v in dic.items():
    for b in range((1<<N)-1):
        if dp[b] == INF: continue
        if b == (b|k): continue
        dp[b|k] = min(dp[b|k], dp[b]+v)
print(-1 if dp[-1]==INF else dp[-1])

Solution (Python):
INF = 10**9 + 7


def main():
    import sys
    input = sys.stdin.buffer.readline
    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)
        bit = 0
        for s in input().split():
            c = int(s)
            bit |= (1 << (c-1))
        C.append(bit)

    dp = [[INF]*(1 << N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i][next_bit] = min(dp[i][next_bit], dp[i][j] + A[i])
    ans = dp[M][(1 << N) - 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
INF = 2*10**7


def main():
    import sys
    input = sys.stdin.buffer.readline
    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)
        bit = 0
        for i in input().split():
            bit |= (1 << (int(i)-1))
        C.append(bit)
    dp = [[INF]*(1 << N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    


if __name__ == '__main__':
    main()

Solution (Python):
INF = 2*10**7


def main():
    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)
        bit = 0
        for i in input().split():
            bit |= (1 << (int(i)-1))
        C.append(bit)
    dp = [[INF]*(1 << N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

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

Solution (Python):
def main():
  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)
    

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

Solution (Python):
def main():
    inf = 10 ** 8 + 1
    N, M = map(int, input().split())

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

    for _ in range(M):
        price, _ = map(int, input().split())
        c = (int(x) - 1 for x in input().split())
        k = sum(1 << x for x in c)
        for bit in reversed(range(1 << N)):
            nbit = bit | k
            dp[nbit] = min(dp[nbit], dp[bit] + price)

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


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
K = []

for _ in range(M):
    a, _ = map(int, input().split())
    k = 0
    for i in map(int, input().split()):
        k |= (1 << (i - 1))
    K.append((a, k))

dp = [10**18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
    for a, k in K:
        dp[state | k] = min(dp[state | k], dp[state] + a)

ans = dp[(1 << N) - 1]
print(ans if ans < 10**18 else -1)

Solution (Python):
INF = 2*10**7


def main():
    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.append({int(i) for i in input().split()})
    dp = [[INF]*(1 << N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] != INF:
                next_bit = j
                for bit in C[i]:
                    next_bit |= (1 << (bit-1))
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    


if __name__ == '__main__':
    main()

Solution (Python):
N, M = list(map(int, input().split()))
ab = []
c = []
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))

A = [10 ** 10] * (1 << N)
C = []
for i in range(M):
  t = 0
  cc = c[i]
  a, b = ab[i]
  for j in cc:
    t |= 1 << (j - 1)
  C.append([t, a])
  A[t] = min(A[t], a)

for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    for j in range(M):
      k, a = n | C[j][0], C[j][1]
      A[k] = min(A[k], A[n] + a)
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

if A[-1] == 10 ** 10:
  print(-1)
else:
  print(A[-1])

Solution (Python):
from itertools import permutations
import sys

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

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

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

main()

Solution (Python):
n,m = map(int,input().split())
x = 2**n
dp = [1000000000 for _ in range(x)]
dp[0] = 0
for i in range(m):
    ai,bi = map(int,input().split())
    c = list(map(int,input().split()))
    bit = 0
    for j in range(bi):
        bit += 2**(c[j]-1)
    for k in range(x):
        dp[k | bit] = min(dp[k | bit],dp[k] + ai)
if dp[x-1] == 1000000000:
    print(-1)
else:
    print(dp[x-1])

Solution (Python):

n,m = list(map(int,input().split()))
price = [0] * m
can_opens = [0] * m
for i in range(m):
    a,b = list(map(int,input().split()))
    price[i]=a
    c = ["0"] * n
    ci = list(map(int,input().split()))
    for j in ci:
        c[n- j]="1"
    can_opens[i]=int("".join(c),2)
inf=float("inf")
dp = [inf] * 2**n
dp[0]=0

for i,(pi,coi) in enumerate(zip(price,can_opens)):
    for j in range(2**n):
        dp[j|coi]=min(dp[j|coi],dp[j]+pi)
from math import isinf
if isinf(dp[-1]):
    print(-1)
else:
    print(dp[-1])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
wv = []
for i in range(m):
    a,b = inpl()
    cnt = 0
    c = inpl()
    for i in c:
        cnt += 1<<(i-1)
    wv.append((a,cnt))
dp = [INF for _ in range(1<<n)]
dp[0] = 0

for i in range(m):
    v,w = wv[i]
    for j in range(1<<n):
        dp[j|w] = min(dp[j|w], dp[j] + v)
print(dp[-1] if dp[-1] != INF else -1)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    g = []
    for _ in range(m):
        a,_ = LI()
        c = LI()
        b = 0
        for i in c:
            b |= 1<<(i-1)
        g.append((b,a))
    B = 1<<n
    dp = [float("inf")]*B
    dp[0] = 0
    for b in range(B):
        for i,v in g:
            nb = b|i
            nd = dp[b]+v
            if nd < dp[nb]:
                dp[nb] = nd
    ans = dp[-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def open(box, key):
    return (box & (2**N-1 - key))
N, M = map(int, input().split())
INF = 10**8+1
dp = [[INF]*2**N for i in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0
key = []
for i in range(M):
    a, b= map(int, input().split())
    n = 0
    c = list(map(int, input().split()))
    for i in range(b):
        n += 2**(c[i]-1)
    key.append((a,n))
for i in range(1,M+1):
    for j in range(2**N):
        dp[i][j] = min(dp[i-1][j], dp[i-1][open(j, key[i-1][1])]+key[i-1][0])
if dp[M-1][2**N-1] == INF:
    dp[M-1][2**N-1] = -1
print(dp[M-1][2**N-1])

Solution (Python):
n,m=map(int,input().split())
keys = []
A = [0]*m
for i in range(m):

    a,b=map(int,input().split())
    A[i] = a
    k = 0
    for c in map(int,input().split()):
        k = k| 2**(c-1)
        
    keys.append(k)



dp = [[10**9]*2**n for i in range(m+1)] 
dp[-1][0] = 0
for i in range(m):
    a = A[i]
    k = keys[i]
    for j in range(2**n):
        dp[i][j|k] = min(dp[i-1][j|k],dp[i-1][j]+a,dp[i][j|k])
        
        
        dp[i][j] = min(dp[i][j],dp[i-1][j]) 
ans = dp[m-1][2**n-1]
if ans ==10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
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:
                
                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])

        
        

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

Solution (Python):





import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def as_bit(ls):
    
    ret = 0
    for l in ls:
        ret ^= 1 << (l - 1)
    return ret


from itertools import product
INF = 10**9
N, M = read_ints()
C = []
A = []
for _ in range(M):
    a, b = read_ints()
    A.append(a)
    c = read_ints()
    C.append(as_bit(c))

'''
dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。

更新則
dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i]) 
dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]) 
∵配るDP。ナンプサックDPの重さの更新がbit演算に置き換わっただけ

初期条件&境界条件
dp[i][bit]=INF
dp[i][0]=0
'''

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

for i in range(M + 1):
    dp[i][0] = 0

for i, bit in product(range(M), range(2 ** N)):
    dp[i + 1][bit | C[i]] = min(dp[i + 1][bit | C[i]], dp[i][bit] + A[i])
    dp[i + 1][bit] = min(dp[i + 1][bit], dp[i][bit])

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

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):

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

Solution (Python):
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)

Solution (Python):
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)

dp = [[1e9]*(1<<n) for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for S in range(1<<n):
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])
        dp[i+1][S|c[i]] = min(dp[i+1][S|c[i]], dp[i][S]+a[i])
if dp[m][(1<<n)-1] < 1e9:
    print(dp[m][(1<<n)-1])
else:
    print(-1)

Solution (Python):

import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

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

sys.setrecursionlimit(10 ** 8)

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

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

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