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):
import sys
INF = int(1e10)
n, m = [int(i) for i in sys.stdin.readline().split()]

key_info = dict()
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    c_ls = [int(i)-1 for i in sys.stdin.readline().split()]
    c_ls = "".join(["1" if c in c_ls else "0" for c in range(n-1,-1,-1)])
    key_info[i] = [a, int(c_ls, 2)]

memo_ls = [[INF for i in range(2**n)] for j in range(m)]

for i in range(m):
    memo_ls[i][0] = 0
    for j in range(2**n):
        memo_ls[i][j] = min(memo_ls[i][j], memo_ls[max(0, i-1)][j])
        memo_ls[i][j | key_info[i][1]] = min(memo_ls[i][j | key_info[i][1]], memo_ls[max(i-1, 0)][j | key_info[i][1]], memo_ls[max(0, i-1)][j] + key_info[i][0])
if memo_ls[-1][-1] == INF:
    print(-1)
else:
    print(memo_ls[-1][-1])

Solution (Python):
N, M = map(int, input().split())
a, b, c = [], [], []
for _ in range(M):
    a_, b_ = map(int, input().split())
    c_ = list( map(int, input().split()) )
    a.append(a_)
    b.append(b_)
    c.append(c_)

INF = 10**9
bit_dp = [INF for _ in range(2**N)]
bit_dp[0] = 0
for i in range(M):
    bit_n = 0
    for j in c[i]:
        bit_n |=  1 << j - 1
    for j in range(2**N):
        if bit_dp[j|bit_n] > bit_dp[j] + a[i]:
            bit_dp[j|bit_n] = bit_dp[j] + a[i]

res = -1 if bit_dp[-1] >= INF else bit_dp[-1]
print(res)

Solution (Python):
N, M = map(int, input().split())
AB_C = [[list(map(int, input().split())) for _ in range(2)] for _ in range(M)]

keys = []
for i, ((a, b), c) in enumerate(AB_C):
    key_flag = 0
    for c_i in c:
        key_flag |= 1<<(c_i-1)
    keys.append((a, key_flag))

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

for i, (price, flag) in enumerate(keys):
    for j in range(1<<N):
        dp[i+1][j] = min(
            dp[i+1][j],
            dp[i][j]
        )
        dp[i+1][j|flag] = min(
            dp[i+1][j|flag],
            dp[i+1][j] + price
        )

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

Solution (Python):

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

C = [float('inf')] * (1 << N)
C[0] = 0
key_v = [float('inf')] * (1 << N)
for j in range(M):
    a, b = map(int, input().split())
    box = list(map(int, input().split()))
    ex_status = 0
    for j in box:
        ex_status += 1 << (j-1)
    key_v[ex_status] = min(a, key_v[ex_status])

for key, val in enumerate(key_v):
    if val == float('inf'):
        continue
    for i in range(1 << N):
        now_status = i
        score = C[now_status] + val
        if score == float("inf"):
            continue

        now_status = i | key

        if C[now_status] > score:
            C[now_status] = score

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

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
a = []
c = []
for i in range(M):
    a_,b=map(int,input().split())
    a.append(a_)
    c_tmp = list(map(int, input().split()))
    tmp=0
    for j in range(len(c_tmp)):
        tmp+=2**(c_tmp[j]-1)
    c.append(tmp)
INF = N*1e+6
dp = [INF]*2**N
dp[0]=0

for i in range(2**N):
    for j in range(M):
        dp[i|c[j]]=min(dp[i|c[j]], dp[i]+a[j])
if dp[2**N-1]==INF:
    print(-1)
    sys.exit()
print(dp[2**N-1])

Solution (Python):

import sys

def solve(N, M, A, B, C):
    key = []  
    for i in range(M):
        s = 0
        for j in range(B[i]):
            s |= 1 << (C[i][j] - 1)
        key.append([s, A[i]])
    
    INF = 1001001001
    dp = [INF] * (1 << N)
    dp[0] = 0
    for s in range(1 << N):
        for i in range(M):
            t = s | key[i][0]
            cost = dp[s] + key[i][1]
            dp[t] = min(dp[t], cost)
    ans = dp[-1]
    print(-1 if ans == INF else ans)
    pass


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A, B, C = [], [], []
    for _  in range(M):
        A.append(int(next(tokens)))
        B.append(int(next(tokens)))
        C.append([int(next(tokens)) for _ in range(B[-1])])
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()

Solution (Python):

def main():
    n, m = map(int, input().split())
    inf = 10**9 
    bit_dp = [inf for _ in range(2**(n))] 
    bit_dp[0] = 0
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bit_n = 0
        for i in c:
            bit_n |= 1 << i - 1 
        for i in range(2**n):
            if bit_dp[i|bit_n] > bit_dp[i] + a:
                bit_dp[i|bit_n] = bit_dp[i] + a
    if bit_dp[-1] >= inf:
        print(-1)
    else:
        print(bit_dp[-1])
                
if __name__ == "__main__":
    main()

Solution (Python):
import math
N, M = map(int, input().split())

INF = 10**9
array_len = int(math.pow(2, N))

min_array = [INF] * array_len

min_array[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c_array = map(int, input().split())
    key_sum = 0
    for c in c_array:
        key_sum += int(math.pow(2, c - 1))
    for i in range(array_len):
        if min_array[i] == INF:
            continue
        else:
            min_array[i | key_sum] = min(min_array[i | key_sum],
                                         min_array[i] + a)

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

Solution (Python):
N, M = map(int, input().split())
pp = []
for _ in range(M):
  a, b = map(int, input().split())
  cc = map(int, input().split())
  bit = 0
  for c in cc:
    bit += 1 << (c - 1)
  pp.append((a, bit))

inf = 10000000

S = 1 << N
dp = [inf] * S
dp[0] = 0
for s in range(1, S):
  for a, bit in pp:
    dp[s] = min(dp[s], a + dp[s - (s & bit)])
if dp[S-1] >= inf:
  print(-1)
else:
  print(dp[S-1])

Solution (Python):

"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

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

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())


dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')


ABT = zip(A, B, totAB)
result = 0

sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)


(x >> i) & 1


dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

add = 1 
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)


li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    


org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)




    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


N, M = list(map(int, input().split()))
AB = [None]*M

C = [0]*M
for m in range(M):
    AB[m] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    key = 0
    for k in c:
        key += 2**(k-1)
    C[m] = key
    
    
def main():
    inf = 10**9
    num_s = 2**N
    dp = [inf]*(num_s)
    dp[0] = 0
    for n in range(num_s):
        for m in range(M):
            l = n | C[m]
            dp[l] = min(dp[l], dp[n]+AB[m][0])
            
    
    
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
ac_lst = []
for i in range(m):
    a, b = map(int, input().split())
    lst = list(map(int, input().split()))
    ac_lst.append((a, lst))
    
dp = [[10**10] * (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_lst = ac_lst[i-1]
    d = 0
    for k in c_lst:
        d = d | (2**(k-1))
    for j in range(2**n):
        k = j | d
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        dp[i][k] = min(dp[i][k], dp[i-1][k], dp[i-1][j] + a)
        
print(dp[-1][-1]) if dp[-1][-1] != 10**10 else print(-1)

Solution (Python):
n,m=map(int,input().split())
arr=[]
for _ in range(m):
  a,b=map(int,input().split())
  tl=list(map(int,input().split()))
  tmp=0
  for val in tl:
    tmp+=2**(val-1)
  arr.append((a,tmp))
dp=[10**18]*(2**n)
dp[0]=0
for val,flag in arr:
  for i in range(2**n-1,-1,-1):
    if dp[i]==10**18:
      continue
    else:
      dp[i|flag]=min(dp[i|flag],dp[i]+val)
if dp[-1]==10**18:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
n,m=map(int,input().split())
arr=[]
for _ in range(m):
  a,b=map(int,input().split())
  tl=list(map(int,input().split()))
  tmp=0
  for val in tl:
    tmp+=2**(val-1)
  arr.append((a,tmp))
dp=[10**18]*(2**n)
dp[0]=0
for val,flag in arr:
  for i in range(2**n-1,-1,-1):
    if dp[i]==10**18:
      continue
    else:
      dp[i|flag]=min(dp[i|flag],dp[i]+val)
if dp[-1]==10**18:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
inf=10**9+7
dp=[inf]*(2**n)
dp[0]=0

for i 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 j in range(2**n):
        dp[j|bit]=min(dp[j|bit],dp[j]+a)

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

Solution (Python):







import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat






def main():
    n, m = map(int, raw_input().split())
    bf, af = [10000000 for i in range(1<<n)], [10000000 for i in range(1<<n)]
    bf[0] = 0
    for i in range(m):
        a, b = map(int, raw_input().split())
        ad = 0
        for st in map(int, raw_input().split()):
            ad |= 1<<(st-1)
        for st in range(1<<n):
            af[st|ad] = min(bf[st]+a, af[st|ad])
            af[st] = min(af[st], bf[st])
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]


main()

Solution (Python):







import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat






def main():
    n, m = map(int, raw_input().split())
    bf, af = [10000000 for i in range(1<<n)], [10000000 for i in range(1<<n)]
    bf[0] = 0
    for i in range(m):
        a, b = map(int, raw_input().split())
        ad = 0
        for st in map(int, raw_input().split()):
            ad |= 1<<(st-1)
        for st in range(1<<n):
            af[st|ad] = min(bf[st|ad], bf[st]+a, af[st|ad])
            af[st] = min(af[st], bf[st])
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]



main()

Solution (Python):
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999




n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
a = []
s = []
for i in range(m):
  aa,bb = inm()
  c = inl()
  ss = 0
  c = [x-1 for x in c]
  for cc in c:
    ss |= (1<<cc)
  a.append(aa)
  s.append(ss)

dp = [BIG] * (2**n)
dp[0] = 0

for i in range(m):
  aa = a[i]
  ss = s[i]
  for j in range(2**n):
    dp[j|ss] = min(dp[j|ss], dp[j]+aa)

v = dp[2**n-1]
print(-1 if v>=BIG else v)

Solution (Python):







import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat






def main():
    n, m = map(int, raw_input().split())
    bf, af = [10000000 for i in range(1<<n)], [10000000 for i in range(1<<n)]
    bf[0] = 0
    for i in range(m):
        a, b = map(int, raw_input().split())
        ad = 0
        for st in map(int, raw_input().split()):
            ad |= 1<<(st-1)
        for st in range(1<<n):
            af[st|ad] = min(bf[st|ad], bf[st]+a, af[st|ad])
        for st in range(1<<n):
            af[st] = min(af[st], bf[st])
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]



main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  a = [None]*(m+1)
  b = [None]*(m+1)
  takara = [0]*m
  for i in range(m):
    ta,tb = (int(i) for i in input().split())
    a[i] = ta
    b[i] = tb
    c = list(int(i) for i in input().split())
    for j in c:
      tmp = j-1
      takara[i] += 1<<tmp
  inf = float("Inf")
  dp = [[inf]*(2**n+1) for _ in range(m+1)]
  dp[0][0] = 0
  for i in range(m):
    for j in range(2**n):
      dp[i+1][j] = min(dp[i][j],dp[i+1][j])
      dp[i+1][j|takara[i]] = min(dp[i][j]+a[i],dp[i+1][j|takara[i]])
  if not dp[m][2**n-1] == inf:
    print(dp[m][2**n-1])
  else:
    print(-1)
solve()

Solution (Python):

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

inf = 10**9

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

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
  
    for j in range(2**n):
        jord = j | d
        dp[jord] = min(dp[jord], dp[j] + a)
            
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return


def B():
    n, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return


def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]


def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return


def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = sum((1<<c[i] for i in range(b)))
        for i in range(1 << n):
            dp[i | fulls] = min(dp[i | fulls], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return


def F():
    return


if __name__ == '__main__':
    E()

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = []
B = []
C = []
for mm in range(M):
    tmpa, tmpb = MAP()
    A.append(tmpa)
    B.append(tmpb)
    tmpc = LIST()
    c = 0
    for cc in tmpc:
        c += 2**(cc-1)
    C.append(c)

dp = [[inf] * (2**N) for _ in range(M+1)]
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 | C[i]] = min(dp[i+1][j | C[i]], dp[i][j] + A[i])
if dp[M][2**N-1] == inf:
    print(-1)
else:
    print(dp[M][2**N-1])

Solution (Python):
N, M = list(map(int, input().split(" ")))
abc = [[0, 0, 0] for i in range(M)]
for i in range(M):
  abc[i][0], abc[i][1] = list(map(int, input().split(" ")))
  c = list(map(int, input().split(" ")))
  for j in c:
    cbits = (1 << j-1) 
    abc[i][2] |= cbits

dp = [0 if i == 0 else float("inf") for i in range(2**N)]
for i in range(M):
  for j in range(2**N):
    if dp[j|abc[i][2]] > dp[j]+abc[i][0]:
      dp[j|abc[i][2]] = dp[j]+abc[i][0]
print(dp[-1] if dp[-1] != float("inf") else -1)

Solution (Python):
def bit_op(i,j):
    a = i&j
    return i ^ a


N = [int(i) for i in input().split()]

a = [0]*N[1]
b = [0]*N[1]
c = []

for k in range(N[1]):
    inp = [int(i) for i in input().split()]
    a[k] = inp[0]
    b[k] = inp[1]

    key = [int(i) for i in input().split()]

    c.append(key)
    




c_two = []

for k in range(N[1]):
    key=0
    for i in range(len(c[k])):
        key = key | 2**(c[k][i]-1)
    
    
    c_two.append(key)



max_j = 2**N[0]

val = [1000000] * max_j

for i in range(N[1]):

    for j in range(max_j):
        j2 = bit_op(j, c_two[i])
        if j2 == 0 :
            if a[i] < val[j] :
                val[j] = a[i]
        else :
            if (val[j2] + a[i]) < val[j]:
                val[j] = val[j2] + a[i]

if val[max_j-1] == 1000000:
    print(-1)
else:
    print(val[max_j-1])

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0
bits = set()
bits.add(0)
for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))
    add_set = set() 
    for j in bits:
        jord = j | d
        dp[jord] = min(dp[jord], dp[j] + a)
        add_set.add(jord)
    bits |= add_set
    
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))  
    for j in range(2**N):
        if dp[j] == INF:
            continue
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    
    d = 0
    for c in c_ls:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))    
    for j in range(2**N):
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Solution (Python):
n,m = map(int,input().split())
vals = []
inf = float("inf")
res = [inf]*2**n

for i in range(m):
	a,b = map(int,input().split())
	C = list(map(int,input().split()))
	cur = 0
	for c in C:
		cur |= 2**(c-1)
	res[cur] = min(res[cur],a)

ans = []
for i,r in enumerate(res):
	if res[i] == inf:
		continue
	ans.append([i,r])


for i,a in ans:
	for j in range(2**n):
		res[i|j] = min(res[i|j],res[i]+res[j])

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

Solution (Python):
def main():
  n,m=map(int,input().split())
  a=[0 for i in range(m)]
  b=[0 for i in range(m)]
  c=[[] for i in range(m)]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
  
  dp=[float("inf") for i in range(2**n)]
  dp[0]=0
  for i in range(m):
    now=0
    for j in c[i]:
      jj=1<<j-1
      now|=jj
    for k in range(2**n):
      kk=k|now
      dp[kk]=min(dp[kk],dp[k]+a[i])
    
 
  if dp[-1]==float("inf"):
    print(-1)
  else:
    print(dp[-1])
    
if __name__ == '__main__':  
  main()

Solution (Python):


N,M=list(map(int,(input().split())))
A=[]
B=[]
C=[]
for x in range(M):
	te,mp=list(map(int,(input().split())))
	A.append(te)
	B.append(mp)
	temp=list(map(int,(input().split())))
	c=0
	for x in temp:
		c+=2**(x-1)
	C.append(c)
dp=[]
for x in range(M+1):
	dp.append([-1]*(2**N))
dp[0][0]=0

for i in range(M):
	for j in range(2**N):
		if (dp[i][j]>=0):
			
			if (dp[i+1][j]==-1):
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=min(dp[i+1][j],dp[i][j])
			
			if (dp[i+1][j|C[i]]==-1):
				dp[i+1][j|C[i]]=dp[i][j]+A[i]
			else:
				dp[i+1][j|C[i]]=min(dp[i+1][j|C[i]],dp[i][j]+A[i])
"""
for x in dp:
	print(x)
print("\n",C)"""
print(dp[M][2**N-1])

Solution (Python):
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())
n, m = rrd()

e = [[] for _i in range(1 << 13)]

p = []
for i in range(m):
    a, b = rrd()
    lst = list(rrd())
    g = 0
    for j in lst:
        g |= 1 << (j - 1)
    p.append((a, g))

for i in range(1 << n):
    for j in p:
        e[i].append((i | j[1], j[0]))
inf = 10**10

dis = [inf] * (1 << 13)
vis = [0] * (1 << 13)
dis[0] = 0

from heapq import *

q = [(0, 0)]
while len(q):
    ds, now = heappop(q)
    if vis[now]:
        continue
    vis[now] = 1
    for next, cost in e[now]:
        if dis[next] > dis[now] + cost:
            dis[next] = dis[now] + cost
            heappush(q, (dis[next], next))

if dis[(1 << n) - 1] == inf:
    print(-1)
else:
    print(dis[(1 << n) - 1])

Solution (Python):
def main():
    n, m = map(int, input().split())
    a = []
    c = []
    dp = [10 ** 7 for j in range(2 ** n)]
    dp[0] = 0
    for _ in range(m):
        a, b = map(int, input().split())
        sc = list(map(int, input().split()))
        c = 0
        for j in sc:
            c += 2 ** (j - 1)
        for j in range(2 ** n):
            dp[j | c] = min(dp[j | c], dp[j] + a)

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


main()

Solution (Python):
import sys
input = sys.stdin.readline


N, M = map(int, input().split())
INF = 10**9
dp = [INF] * (2**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(2**N):
    if dp[i|bit] > dp[i] + a:
      dp[i|bit] = dp[i] + a
if dp[-1] >= INF:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
MAX = 10000000

memo = [MAX for i in range(10000)]
memo[0] = 0
a = []
c = []
for i in range(M):
	tmpa, tmpb = map(int, input().split())
	tmpc = list(map(int, input().split()))
	bitc = 0
	for tmp in tmpc:
		tmp = tmp - 1
		bitc = bitc | (1<<tmp)
	a.append(tmpa)
	c.append(bitc)

for i in range(M):
	cost = a[i]
	bit = c[i]
	for idx in range(10000 - 1, -1, -1):
		if(memo[idx] < MAX):
			to = idx | bit
			memo[to] = min(memo[to], memo[idx] + cost)
if(memo[2**N - 1] != MAX):
	print(memo[2**N-1])
else:
	print(-1)

Solution (Python):
def main():
    N,M = map(int, input().split())

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

    for i in range(M):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        bit_c = 0
        for bi in c:
            bit_c |= 1 << bi-1
        
        for j in range(2**N):
            dp[j|bit_c] = min(dp[j] + a, dp[j|bit_c])

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


if __name__ == "__main__":
    main()

Solution (Python):


from collections import defaultdict

MX = 10**10


def getInt(cn):
  ret = 0
  for c in cn:
    ret += 2**(c-1)
  return ret



N,M = map(int, input().split())
Prices = defaultdict(lambda:MX)
for _ in range(M):
  a,b = map(int, input().split())
  cn = list(map(int, input().split()))
  Prices[getInt(cn)] = min(Prices[getInt(cn)],a)

dp = [MX for _ in range(2**N)]
dp[0] = 0
for p in Prices:
  for i in range(2**N):
    dp[i|p] = min(dp[i|p],dp[i]+Prices[p])

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

Solution (Python):
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 x in c:
      key += 2 **(x-1)
    
    ndp = dp.copy()
    for j in range(2**N):
        if dp[j | key] > ndp[j] + a:
            dp[j | key] = ndp[j] + a
            
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Solution (Python):
INF = float('inf')
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N):
        temp = dp[i] + a
        if dp[i|open_bit] > temp: dp[i|open_bit] = temp
if dp[-1] != INF: print(dp[-1])
else: print(-1)

Solution (Python):
INF = float('inf')
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N):
        temp = dp[i] + a
        if dp[i|open_bit] > temp: dp[i|open_bit] = temp
print(dp[-1] if dp[-1] != INF else -1)

Solution (Python):
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dp = [INF for _ in range(2**N)]
    dp[0] = 0
    for i in range(M):
        a, _ = map(int, input().split())
        *C, = map(int, input().split())
        open_bit = 0
        for i in C: open_bit |= 1 << i-1
        for i in range(2**N): dp[i|open_bit] = min(dp[i|open_bit], dp[i] + a)
    print(dp[-1] if dp[-1] != INF else -1)
if __name__ == '__main__':
    main()

Solution (Python):

N, K = map(int, input().split())
key_data_list = []
for _ in range(K):
    value, op = map(int, input().split())
    open_boxes = map(int, input().split())
    box_value = 0
    for opb in open_boxes:
      box_value += 2**(opb-1)
    key_data_list.append([value, box_value])

max_tresure_state = 2**N
max_key_price = 2**30
dp_table = [[max_key_price] * (max_tresure_state) for i in range(K+1)]

dp_table[0][0] = 0

for key_index in range(K):
    for tresure_state in range(max_tresure_state):
        key_value = key_data_list[key_index][0]
        key_state = key_data_list[key_index][1]

        if dp_table[key_index+1][tresure_state] > dp_table[key_index][tresure_state]:
            dp_table[key_index+1][tresure_state] = dp_table[key_index][tresure_state]

        buying_state = key_state | tresure_state
        dp_table[key_index+1][buying_state] = min(dp_table[key_index][buying_state],
                                                  dp_table[key_index+1][buying_state],
                                                  dp_table[key_index][tresure_state] + key_value)


result_value = dp_table[K][max_tresure_state-1]
if result_value == max_key_price:
    print(-1)
else:
    print(int(result_value))