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
input = sys.stdin.readline
from pprint import pprint
N, M = map(int, input().split())
A = [-1]*M
B = [-1]*M
C = [-1]*M

for i in range(M):
    A[i], B[i] = map(int, input().split())
    ls = list(map(int, input().split()))
    c = 0
    for j in range(len(ls)):
        c += 2 ** (ls[j]-1)
    C[i] = c


dp = [[float('inf')]*(2**N) for _ in range(M)]

j = 0
for i, di in enumerate(C):
    if i == 0:
        dp[i][di] = A[i]
        dp[i][0] = 0
        continue
    for j in range(2**N):
        stay = dp[i - 1][j | di]
        buy = dp[i - 1][j] + A[i]
        now = dp[i][j | di]
        dp[i][j | di] = min(stay, buy, now)
    for j in range(2**N):
        dp[i][j] = min(dp[i][j], dp[i-1][j])

ans = dp[-1][2**N-1]
if ans > sum(A):
    print(-1)
else:
    print(ans)

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=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):
import sys
input=sys.stdin.readline
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=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):
box_num, key_num = map(int, input().split())
dp_length = 2**box_num
dp = [float('inf')] * dp_length
dp[0] = 0
for _ in range(key_num):
    current_key_price, _ = map(int, input().split())
    c = 0
    effects = list(map(int, input().split()))
    for i in effects:
        e = 1 << (i - 1)
        c += e
    for x in range(dp_length):
        new_price = dp[x] + current_key_price
        dp_index = c | x
        if dp[dp_index] > new_price:
            dp[dp_index] = new_price
    
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

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

inf = 10 ** 10

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

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

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

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

Solution (Python):
import itertools

N,M = map(int, input().split())
A = []
C = []
comp = sum(1<<int(x) for x in range(N))
for m in range(M):
  a, b = map(int, input().split())
  A.append(a)
  c = list(map(int, input().split()))
  C.append(sum(1<<(int(x)-1) for x in c))

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

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

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

Solution (Python):
n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    csbit = 0
    for j in cs[i]:
        csbit += 2**(j-1)
    for j in range(1 << n):
        dp[j | csbit] = min(dp[j | csbit], dp[j] + ab[i][0])

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

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

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

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


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

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

Solution (Python):
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import 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 list(map(lambda x: int(x)-1, 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)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return




def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return




def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return




def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    
    
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            
        if g == 1:
            break
        if i == sq - 1:
            
            ans += 1

    print(ans)

    return




def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit += 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

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

    return




def F():
    N, M = map(int, input().split())

    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        unlock = 0
        for i in range(1, N+1):
            if i in c:
                unlock += 2 ** (i-1)
        key.append((a, unlock))

    dp = [[float('inf') for _ in range(2 ** N)] for _ in range(M + 1)]
    dp[0][0] = 0
    for i in range(M):
        for state in range(2 ** N):
            next_state = state | key[i][1]
            dp[i+1][next_state] = min(dp[i][state] + key[i]
                                      [0], dp[i+1][next_state])
        for state in range(2 ** N):
            dp[i+1][state] = min(dp[i+1][state], dp[i][state])

    if dp[-1][-1] < 10 ** 10:
        print(dp[-1][-1])
    else:
        print(-1)
    return



if __name__ == '__main__':
    E()

Solution (Python):
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import 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 list(map(lambda x: int(x)-1, 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)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return




def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return




def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return




def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    
    
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            
        if g == 1:
            break
        if i == sq - 1:
            
            ans += 1

    print(ans)

    return




def E():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k-1] = '1'
        bin = ''.join(L)
        power[i] = int(bin, 2)
    bin = ''.join(list(['1'] * N))
    
    dp = [[inf for i in range(int(bin, 2)+1)] for j in range(M+1)]
    dp[0][0] = 0

    
    
    for i in range(M):

        for w in range(int(bin, 2) + 1):

            t = w | power[i]
            cost = dp[i][w] + value[i]

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

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

    return




def F():
    N, M = map(int, input().split())

    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        unlock = 0
        for i in range(1, N+1):
            if i in c:
                unlock += 2 ** (i-1)
        key.append((a, unlock))

    dp = [[float('inf') for _ in range(2 ** N)] for _ in range(M + 1)]
    dp[0][0] = 0
    for i in range(M):
        for state in range(2 ** N):
            next_state = state | key[i][1]
            dp[i+1][next_state] = min(dp[i][state] + key[i]
                                      [0], dp[i+1][next_state])
        for state in range(2 ** N):
            dp[i+1][state] = min(dp[i+1][state], dp[i][state])

    if dp[-1][-1] < 10 ** 10:
        print(dp[-1][-1])
    else:
        print(-1)
    return



if __name__ == '__main__':
    E()

Solution (Python):
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import 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 list(map(lambda x: int(x)-1, 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)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return




def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return




def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return




def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    
    
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            
        if g == 1:
            break
        if i == sq - 1:
            
            ans += 1

    print(ans)

    return




def E():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return




def F():
    return



if __name__ == '__main__':
    E()

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

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

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

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

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

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

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

Solution (Python):
import numpy as np
N, M = list(map(int, input().split(" ")))
dp = [np.inf] * (1 << N)
dp[0] = 0
bits = set()
bits.add(0)

for i in range(M):
    val,b = list(map(int, input().split(" ")))
    opens = list(map(int, input().split(" ")))
        
    
    keybits = 0
    for tmp in opens:
        keybits += 1 << tmp-1
    
    for prev in list(bits):
        target = prev | keybits
        dp[target] = min(dp[target], dp[prev]+val)
        bits.add(target)
    
print(dp[-1] if dp[-1] != np.inf else -1)

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

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

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

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
P = 2**N
INF = 10**12
cost = [INF]*P
cost[0] = 0
for _ in range(M):
    a, b = inpl()
    c = inpl()
    k = 0
    for ci in c:
        k |= 1<<(ci-1)
    for i in range(P):
        new = i | k
        cost[new] = min(cost[new],cost[i]+a)

ans = cost[P-1]
if ans >= INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """2 3
10 1
1
15 1
2
30 2
1 2"""
        output = """25"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """12 1
100000 1
2"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """69942"""
        self.assertIO(input, output)
def resolve():
    (N,M)=(int(i) for i in input().split())
    housekis=[]
    for i in range(M):
        (a,b)=(int(i) for i in input().split())
        ability=sum([2**(int(i)-1) for i in input().split()])
        housekis.append([a,ability])
    dpt=[[1<<29 for i in range(2**N)] for j in range(M+1)]
    dpt[0][0]=0
    for i in range(M):
        for j in range(2**N):

            dpt[i+1][j]=min(dpt[i][j],dpt[i+1][j])
            dpt[i+1][j | housekis[i][1]]=min(dpt[i+1][j | housekis[i][1]],housekis[i][0]+dpt[i][j])

    if dpt[-1][-1]==1<<29:
        print(-1)
    else:
        print(dpt[-1][-1])


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())

dp = [float("inf")]*(1<<n)
dp[0] = 0
for _ in [0]*m:
    a,b = map(int,input().split())
    sc = 0
    for e in map(int,input().split()):
        sc += 1<<(e-1)
    
    for i in range(1<<n):
        dp[i|sc] = min(dp[i|sc],dp[i]+a)


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

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

INF = int(10e8 + 1)
dp = [INF] * (1 << n)
dp[0] = 0

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

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

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

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

Solution (Python):
import heapq
N,M=map(int,input().split())
a=[0 for i in range(M)]
c=[0 for i in range(M)]
for i in range(M):
    a[i],b=map(int,input().split())
    tmp=[int(i)-1 for i in input().split()]
    for j in tmp:
        c[i]+=2**j
edge=sorted([(a[i],c[i]) for i in range(M)])
q=[]
heapq.heappush(q,(0,0))
dist=[10**15 for i in range(2**N)]
dist[0]=0
while(len(q)!=0):
    prc,src=heapq.heappop(q)
    if dist[src]<prc:
        continue
    for e in edge:
        cost,nxt=e
        dest=nxt|src
        if dest==src:
            continue
        if dist[dest]>dist[src]+cost:
            dist[dest]=dist[src]+cost
            heapq.heappush(q,(dist[dest],dest))
ans=dist[-1]
if ans==10**15:
    print(-1)
else:
    print(ans)

Solution (Python):
def e_get_everything(INF=float('inf')):
    
    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(sum(1 << (t - 1) for t in [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])
            
            next_j = j | C[i]  
            dp[i + 1][next_j] = min(dp[i + 1][next_j], dp[i][j] + A[i])
    
    return dp[M][(1 << N) - 1] if dp[M][(1 << N) - 1] != INF else -1

print(e_get_everything())

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

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

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

Solution (Python):
from math import isinf

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

a = [0 for _ in range(M + 1)]
k = [0 for _ in range(M + 1)]
for i in range(M):
    a_i, _ = map(int, input().split())
    a[i + 1] = a_i
    k_i = 0
    for c in map(int, input().split()):
        k_i = k_i | 2 ** (c - 1)
    k[i + 1] = k_i

dp = [[float('inf') for _ in range(2 ** N)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(1, M + 1):
    for s in range(2 ** N):
        
        dp[i][s] = min(dp[i][s], dp[i - 1][s])
        
        dp[i][s | k[i]] = min(dp[i][s | k[i]], dp[i - 1][s] + a[i])

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

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

inf=10**8

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

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

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

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

Solution (Python):
inf=10**8

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

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

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

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

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

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

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

for i in range(M-1):


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

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

Solution (Python):
N,M = map(int,input().split())
A = []
B = []
C = []
for i in range(M):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)
  c = list(map(int,input().split()))
  C.append(c)




INF = 10**9+7
dp = [INF for _ in range(1<<N)]
dp[0] = 0
for j in range(1<<N):
  for i in range(M):
    t = 0
    for c in C[i]:
      t |= 1<<(c-1)
    dp[j|t] = min(dp[j|t], dp[j] + A[i])
    

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

Solution (Python):
import itertools
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1 << (int(x)-1) for x in readline().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

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

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

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

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

C = []
dp = [10 ** 9 for i in range (1 << N)]
dp [0] = 0
for i in range(M):
  a, b = map(int, input().split())
  c = list(map(lambda x: int(x) - 1, input().split()))
  b = 0
  for i in c:
    b |= 1 << i
  C.append((b,a))
for s in range(1 << N):
  for c in range(M):
    t = s | C[c][0]
    dp[t] = min(dp[t], dp[s] + C[c][1])
print (dp[-1] if dp[-1] != 10 ** 9 else -1)

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

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

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

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

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

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

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



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

Solution (Python):
INF=10**9
N,M=map(int,input().split())
L=[]
for i in range(M):
  a,b=map(int,input().split())
  l=[]
  l.append(a)
  l.append(b)
  c=list(map(int,input().split()))
  c_=0
  for j in c:
    c_+=2**(j-1)
  l.append(c_)
  L.append(l)

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

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

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


dp[0] = 0

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

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

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






inf=int(1e10)
dp=[inf]*(2**n)


bits=set()


dp[0]=0

bits.add(0)

for _ in range(m):
  cost,kind=map(int,input().split())
  
  key=list(map(int,input().split()))
  keyBit=0
  
  
  for temp in key:
    keyBit+=2**(temp-1)
  
  
  for item in list(bits):
    temp=item|keyBit
    dp[temp]=min(dp[temp],dp[item]+cost)
    bits.add(temp)

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

Solution (Python):
from subprocess import*
with open('e.cpp','w')as f:f.write(r"""

using namespace std;

const int maxs = 4096;
int dp[maxs];

int main() {
	memset(dp, 0x3f, 16384);
	dp[0] = 0;
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b, s = 0;
		cin >> a >> b;
		while (b--) {
			int c;
			cin >> c;
			s ^= 1 << c - 1;
		}
		dp[s] = min(dp[s], a);
	}
	for (int i = 0; i != n; ++i) for (int all = (1 << n) - 1 ^ 1 << i, sub = all; sub; sub = sub - 1 & all)
		dp[sub] = min(dp[sub], dp[sub ^ 1 << i]);
	for (int s = 0; s != (1 << n); ++s) if (s != (s & -s))
		for (int t = s - 1 & s; t != s; t = t - 1 & s)
			dp[s] = min(dp[s], dp[t] + dp[s ^ t]);
	int mask = (1 << n) - 1;
	if (dp[mask] == 0x3f3f3f3f) dp[mask] = -1;
	cout << dp[mask] << endl;
}""")
call(('g++','e.cpp'))
call('./a.out')

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

Solution (Python):
import heapq
N,M=map(int,input().split())
a=[0 for i in range(M)]
c=[0 for i in range(M)]
for i in range(M):
    a[i],b=map(int,input().split())
    tmp=[int(i)-1 for i in input().split()]
    for j in tmp:
        c[i]+=2**j
edge=sorted([(a[i],c[i]) for i in range(M)])
q=[]
heapq.heappush(q,(0,0))
dist=[10**15 for i in range(2**N)]
dist[0]=0
while(len(q)!=0):
    prc,src=heapq.heappop(q)
    if dist[src]<prc:
        continue
    for e in edge:
        cost,nxt=e
        dest=nxt|src
        if dest==src:
            continue
        if dist[dest]>dist[src]+cost:
            dist[dest]=dist[src]+cost
            heapq.heappush(q,(dist[dest],dest))
ans=dist[-1]
if ans==10**15:
    print(-1)
else:
    print(ans)

Solution (Python):
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import heapq

import logging
logging.basicConfig(level=logging.DEBUG)

import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

MOD = 10**9+7
INF = float('inf')

"""


5 5
10 2
1 3
15 2
2 4
5 2
3 5
20 1
5
20 4
1 2 3 4


25
"""

def main():
    N,M=[int(x) for x in input().split()]
    dp = [INF] * 2**N
    dp[0]=0
    for i in range(M):
        a,b=[int(x) for x in input().split()]
        c=sum([1 << (p-1) for p in list(map(int, input().split()))])
        for j in range(2**N):
            dp[j|c]=min(dp[j|c], dp[j]+a)
    print(dp[-1] if dp[-1]!=INF else -1)

main()

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