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):
def main():
    n,m = tuple([int(t)for t in input().split()])

    keys = []

    dp = [10**9]*(1<<n)
    dp[0] = 0
    for _ in range(m):
        a,_ = tuple([int(t)for t in input().split()])
        c = tuple([int(t)for t in input().split()])
        key = 0
        for c_i in c:
            key |= 1<<(c_i-1)
        keys.append((a,key))
    

    for a,key in keys:
        for i in range(1<<n):
            dp[i|key] = min(dp[i|key],dp[i]+a)

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

Solution (Python):
def main():
    n,m = tuple([int(t)for t in input().split()])

    keys = []

    dp = [10**9]*(1<<n)
    dp[0] = 0
    for _ in range(m):
        a,_ = tuple([int(t)for t in input().split()])
        c = tuple([int(t)for t in input().split()])
        key = 0
        for c_i in c:
            key |= 1<<(c_i-1)
        keys.append((a,key))
    

    for a,key in keys:
        for i in range(1<<n):
            dp[i|key] = min(dp[i|key],dp[i]+a)

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

Solution (Python):
def solve():
  ans = 0
  N, M = map(int, input().split())
  A,C = [0]*M,[0]*M
  for i in range(M):
    A[i],b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(b):
      C[i] += 1<<(c[j]-1)
  dp = [float('inf')]*(1<<N)
  dp[0] = 0
  for i in range(1,(1<<N)+1):
    for key in range(M):
      if C[key] & i == 0:
        continue
      dp[i] = min(dp[i],dp[i&~C[key]]+A[key])
  ans = dp[-1]
  if ans==float('inf'):
    return -1
  return ans
print(solve())

Solution (Python):
import sys
from collections import defaultdict, deque, Counter
import math
 

from bisect import bisect_left, bisect_right

 

 

input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 

def makebin(arr):
    ret = 0
    for num in arr:
        ret += 2 ** (num - 1)

    return ret

def main():
    n, m = getList()
    dp = [INF] * (2 ** n)
    dp[0] = 0
    for i in range(m):
        a, b = getList()
        tgt = getList()
        kagi = makebin(tgt)
        for i, d in enumerate(dp):
            if d != -1:
                dp[i|kagi] = min(dp[i|kagi], d + a)
        

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






 
if __name__ == "__main__":
    main()

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

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

INF = 10 ** 9
dp = [INF] * (2 ** N)
dp[0] = 0
for i in range(M):
  a,b = map(int,readline().split())
  C = list(map(int,readline().split()))
  key = 0
  for c in C:
    key += (1 << (c - 1))
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    if dp[j | key] > dp[j] + a:
      dp[j | key] = dp[j] + a

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

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

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

INF = 10 ** 9
dp = [INF] * (2 ** N)
dp[0] = 0
for i in range(M):
  a,b = map(int,readline().split())
  C = list(map(int,readline().split()))
  key = 0
  for c in C:
    key += (1 << (c - 1))
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    dp[j | key] = min(dp[j | key], dp[j] + a)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    keys = []
    for _ in range(m):
        bit = ["0"] * n
        a, b = map(int, input().split())
        C = map(int, input().split())
        for c in C:
            bit[c - 1] = "1"
        bit = int("".join(bit), 2)
        keys.append([bit, a])

    dp = [f_inf] * (1 << n)
    dp[0] = 0
    for i in range(1 << n):
        for k, cost in keys:
            idx = i | k
            dp[idx] = min(dp[idx], dp[i] + cost)

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

input = sys.stdin.readline
INF = float("inf")


def main():
    N, M = map(int, input().split())
    keys = [None] * M
    for i in range(M):
        a, b = map(int, input().split())
        s = 0
        for c in map(int, input().split()):
            c -= 1
            s |= 1 << c
        keys[i] = (s, a)

    dp = [INF] * (2 ** N)
    dp[0] = 0
    for s in range(2 ** N):
        for key, a in keys:
            t = s | key
            dp[t] = min(dp[t], dp[s] + a)

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


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
bit = [int(1e18) for _ in range(1 << N)]
bit[0] = 0
F = {0}
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bas = 0
  for k in range(b):
    c[k] -= 1
    bas += (1 << c[k])
  L = [[j, bit[j]] for j in F]
  for j in L:
    tb = 0
    for k in range(N):
      tb += (((j[0] >> k) & 1) | ((bas >> k) & 1)) << k
    bit[tb] = min(bit[tb], j[1] + a)
    F.add(tb)
if bit[-1] != int(1e18):
  print(bit[-1])
else:
  print(-1)

Solution (Python):
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    cc = list(map(int, input().split()))
    for ccc in cc:
        ccc -= 1
        c[i] += (1 << ccc)

INF = float('inf')
dp = [[INF]*5000 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])
        nj = j | c[i]
        dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + a[i])
if dp[M][(1 << N)-1] == INF:
    print(-1)
else:
    print(dp[M][(1 << N)-1])

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

abcsl = []
for _ in range(m):
    a,b = map(int, input().split())
    cl = list(map(int, input().split()))
    abcsl.append((a,b,cl))


dp = [10**9]*(2**n)
dp[0] = 0
for a,b,cl in abcsl:
    b_bit = 0
    for c in cl:
        b_bit += 2**(c-1)
    for i in range(2**n):
        dp[i|b_bit] = min(dp[i]+a, dp[i|b_bit])

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

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

abcsl = []
for _ in range(m):
    a,b = map(int, input().split())
    cl = list(map(int, input().split()))
    abcsl.append((a,b,cl))


dp = [10**9]*(2**n)
dp[0] = 0
for a,b,cl in abcsl:
    b_bit = 0
    for c in cl:
        b_bit += 2**(c-1)
    for i in range(2**n):
        dp[i|b_bit] = min(dp[i]+a, dp[i|b_bit])

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

Solution (Python):
n,m = map(int,input().split())
p = []
for k in range(m):  
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    key = 0
    for i in c:
        key += 2**(i-1)
    p.append([a,key])
inf = 10**9
dp = []
for u in range(m+1):
    dp.append([inf for i in range(2**n)])
dp[0][0] = 0
for i in range(m):
    for k in range(2**n):
        dp[i+1][k] = dp[i][k]
    for k in range(2**n):
        dp[i+1][k|p[i][1]] = min(dp[i][k|p[i][1]],dp[i][k]+p[i][0],dp[i+1][k|p[i][1]])
if dp[-1][-1] == inf:
    print(-1)
else:
    print(dp[-1][-1])

Solution (Python):


import sys
input = sys.stdin.buffer.readline
INF = float("inf")

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

    
    dp = [[INF for _ in range(2**N)] 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()))

        
        bit = 0
        for x in c:
            bit |= 1 << (x-1)
        
        for j in range(2**N):
            
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
ab=[]
c=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
  c.append(list(map(int,input().split())))
dp={'0'*n:0}
for i in range(m):
  a,b=ab[i]
  ci=c[i]
  dptmp={}
  for k,v in dp.items():
    s=list(k)
    for cii in ci:
      s[cii-1]='1'
    t=''.join(s)
    dptmp[t]=min(v+a,dp[t] if t in dp else float('inf'),dptmp[t] if t in dptmp else float('inf'))
  dp.update(dptmp)

t='1'*n
if t in dp:
  print(dp[t])
else:
  print(-1)

Solution (Python):
N, M = map(int, input().split())
X = []
Y = []
for _ in range(M):
    X.append(list(map(int, input().split())))
    
    tmp = 0
    for i in list(map(int, input().split())):
        tmp += 2 ** (i - 1)
    Y.append(tmp)

inf = 10 ** 9 + 7
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 | Y[i]] = min(dp[i + 1][j | Y[i]],
                                  dp[i][j] + X[i][0])

ans = min(dp[i][-1] for i in range(M + 1))
print(ans if ans < inf else -1)

Solution (Python):
INF = 10 ** 18
N, M = map(int, input().split())
dp = [[INF for _ in range(1 << N)] for _ in range(M + 1)]
cost = [0] * M
bit = [0] * M
for i in range(M):
    cost[i], b = map(int, input().split())
    c = list(map(int, input().split()))
    d = 0
    for j in range(len(c)):
        d |= 1 << (c[j] - 1)
    bit[i] = d

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])
        to = bit[i] | j
        dp[i + 1][to] = min(dp[i + 1][to], dp[i][j] + cost[i])

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

Solution (Python):
ans = 10 ** 7
n, m = map(int, input().split())
dp = [float('inf')] * (2 ** n)
dp[0] = 0
prices = []
for i in range(m):
    a, s = map(int, input().split())
    prices.append(a)
    f = 0
    for k in map(int, input().split()):
        f += 2 ** (k - 1)
    for j in range(2 ** n - 1, -1, -1):
        dp[j | f] = min(dp[j] + a, dp[j | f])
print(-1 if dp[-1] == float('inf') else dp[-1])

Solution (Python):



def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = [MAX] * (2 ** 13)
  dp[0] = 0
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(len(dp)):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if dp[2**(n+1)-2] != MAX:
    print(dp[2**(n+1)-2])
  else:
    print(-1)

if __name__=='__main__':
  main()

Solution (Python):
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()



def solve():
    n,m = invr()
    q = 1 << n
    w = [10 ** 18] * q
    w[0] = 0
    for i in range(m):
        a,b = invr()
        qw = 0
        for j in map(int,input().split()):
            qw = qw + (1 << (j - 1))
        for j in range(q - 1,-1,-1):
            w[j|qw] = min(w[j] + a,w[j | qw])
    print(-1 if w[-1] == 10 ** 18 else w[-1])
    


 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))


ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n, m = map(int, input().split())
    key = []  
    for i in range(m):
        a, b = map(int, input().split())
        s = 0
        C = list(map(int, input().split()))
        for j in range(b):
            C[j] -= 1
            s |= 1 << C[j]  
        key.append((s, a))
    INF = 10**9+7
    dp = [INF]*(2**n)
    dp[0] = 0

    for s in range(2**n):
        for i in range(m):
            t = s | key[i][0]
            cost = dp[s]+key[i][1]
            dp[t] = min(dp[t], cost)

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


resolve()

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

INF = 1001001001
dp = [INF] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for k, v in keys:
        t = s | k
        cost = dp[s] + v
        dp[t] = min(dp[t], cost)

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

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

INF = 1001001001
dp = [INF] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for k, v in keys:
        t = s | k
        cost = dp[s] + v
        dp[t] = min(dp[t], cost)

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

Solution (Python):
def main():
    INF = 10 ** 10
    N, M = list(map(int, input().split(' ')))
    key_list = list()
    for _ in range(M):
        A, _ = list(map(int, input().split(' ')))
        C = list(map(lambda x: int(x) - 1, input().split(' ')))
        boxes = 0
        for c in C:
            boxes |= (1 << c)
        key_list.append((A, boxes))
    
    
    dp = [[INF for _ in range(1 << N)] for _ in range(M + 1)]
    for m in range(M + 1):
        dp[m][0] = 0
    for m in range(1, M + 1):
        cost, box = key_list[m - 1]
        for S in range(1 << N):
            dp[m][S] = min(dp[m][S], dp[m - 1][S])
            if box | S != S:
                dp[m][box | S] = min(dp[m][box | S], dp[m - 1][S] + cost)
    ans = dp[M][(1 << N) - 1]
    if ans >= INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
dp = [float("INF")]*(1<<n)
dp[0] = 0
for _ in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    C = 0
    for e in c:
        C += 1<<(e-1)
    for i in range(1<<n): 
        dp[i|C] = min(dp[i|C], dp[i]+a)
if dp[-1] == float("INF"): print(-1)
else: print(dp[-1])

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = sum(1 << (int(s) - 1) for s in readline().split())

    dp = [INF] * (1 << N)
    dp[0] = 0
    for S in range(1 << N):
        if dp[S] == INF:
            continue
        for a, c in zip(A, C):
            if dp[S | c] > dp[S] + a:
                dp[S | c] = dp[S] + a

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = sum(1 << (int(s) - 1) for s in readline().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):
            if dp[i + 1][j] > dp[i][j]:
                dp[i + 1][j] = dp[i][j]
            if dp[i + 1][j | C[i]] > dp[i][j] + A[i]:
                dp[i + 1][j | C[i]] = dp[i][j] + A[i]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = ~sum(1 << (int(s) - 1) for s in readline().split())

    dp = [INF] * (1 << N)
    dp[0] = 0
    for bit in range(1 << N):
        for a, c in zip(A, C):
            if dp[bit & c] < INF:
                dp[bit] = min(dp[bit], dp[bit & c] + a)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], b = map(int, readline().split())
        C[i] = sum(1 << (int(s) - 1) for s in readline().split())

    dp = [INF] * (1 << N)
    dp[0] = 0
    for bit in range(1 << N):
        for a, c in zip(A, C):
            if dp[bit & ~c] < INF:
                dp[bit] = min(dp[bit], dp[bit & ~c] + a)

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


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
INF=10**10
dp=[[INF]*(1<<n) for _ in range(m+1)]
for i in range(m+1):
    dp[i][0]=0
a=[0]
key=[0]
for i in range(m):
    a0,b=map(int,input().split())
    a.append(a0)
    *c,=map(int,input().split())
    tmp=0
    for j in c:
        tmp+=1<<(j-1)
    key.append(tmp)

for i in range(1,m+1):
    for j in range(1<<n):
        if dp[i-1][j]<INF:
            dp[i][j]=min(dp[i][j],dp[i-1][j])
            dp[i][j|key[i]]=min(dp[i][j|key[i]],dp[i-1][j|key[i]],dp[i-1][j]+a[i])

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

Solution (Python):
n,m=map(int,input().split())
g=(1<<n)
dp=[10**18]*g
dp[0]=0
for i in  range(m):
    a,s=map(int,input().split())
    f=0
    for k in map(int,input().split()):
        f+=1<<(k-1)
    for j in range(g-1,-1,-1):
        dp[j|f]=min(dp[j]+a,dp[j|f])
print(-1 if dp[-1]==10**18 else dp[-1])

Solution (Python):
ans=10**7
n,m=map(int,input().split())
dp=[10**18]*(2**n)
dp[0]=0
prices=[]
for i in  range(m):
    a,s=map(int,input().split())
    prices.append(a)
    f=0
    for k in map(int,input().split()):
        f+=2**(k-1)
    for j in range(2**n-1,-1,-1):
        dp[j|f]=min(dp[j]+a,dp[j|f])
print(-1 if dp[-1]==10**18 else dp[-1])

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

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

    s=0
    for cc in c:
        s+=2**(cc-1)
    
    for j in range(2**N):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|s]=min(dp[i+1][j|s],dp[i][j]+a)
    
print(dp[M][2**N-1] if dp[M][2**N-1]<inf else -1)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, M = getNM()
weight = []
value = []
for i in range(M):
    a, b = getNM()
    c = getList()
    weight.append(a)
    value.append(c)
"""
N, M = 4, 6
weight = [67786, 3497, 44908, 2156, 26230, 86918]
value = [[1, 3, 4], [2], [2, 3, 4], [2, 3, 4], [2], [3]]
"""




def get_everything(n, weight, value):
    m = len(weight)
    dp = [float("inf")] * (1 << n)
    dp[0] = 0

    for i in range(m):
        bit = 0
        for item in value[i]:
            bit |= (1 << (item - 1))

        for j in range(1 << n):
            dp[j | bit] = min(dp[j | bit], dp[j] + weight[i])

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

ans = get_everything(N, weight, value)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

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

keys=[[] for _ in range(N)]
dp=[-1]*(2**N)
dp[0]=0

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

    op=2**N-1

    for cc in c:
        op-=2**(cc-1)

    for cc in c:
        keys[cc-1].append((op,a))


def rec(current):
    if dp[current]>-1:
        return dp[current]

    ret=10**10

    i=0
    tmp=current
    while tmp&1==0:
        i+=1
        tmp=tmp>>1
    
    for op,a in keys[i]:
        minc=rec(current&op)
        ret=min(ret,a+minc)
    
    if ret==10**10:
        print(-1)
        exit(0)
    
    dp[current]=ret
    return ret

print(rec(2**N-1))

Solution (Python):
n, m = map(int, input().split())
a, b, c = [], [], []
for i in range(m):
    ai, bi = map(int, input().split())
    a.append(ai); b.append(bi)
    ci = list(map(int, input().split()))
    c.append(ci)

dp = [[10**9 for j in range(2**n)] for i in range(m)]
key = 0
for i in range(b[0]):
    key += 1<<(c[0][i]-1)
dp[0][key] = a[0]
dp[0][0] = 0

for i in range(1, m):
    ai, bi, ci = a[i], b[i], c[i]
    key = 0
    for j in range(bi):
        key += 1<<(ci[j]-1)
    for j in range(2**n):
        dp[i][j|key] = min(dp[i-1][j|key], dp[i-1][j]+ai, dp[i][j|key])
    for j in range(2**n):
        dp[i][j] = min(dp[i-1][j], dp[i][j])

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

Solution (Python):
n, m = map(int, input().split())
a, b, c = [], [], []
for i in range(m):
    ai, bi = map(int, input().split())
    a.append(ai); b.append(bi)
    ci = list(map(int, input().split()))
    c.append(ci)

dp = [[10**9 for j in range(2**n)] for i in range(m)]
for i in range(m):
    dp[i][0] = 0
key = 0
for i in range(b[0]):
    key += 1<<(c[0][i]-1)
dp[0][key] = a[0]

for i in range(1, m):
    ai, bi, ci = a[i], b[i], c[i]
    key = 0
    for j in range(bi):
        key += 1<<(ci[j]-1)
    for j in range(2**n):
        dp[i][j|key] = min(dp[i-1][j|key], dp[i-1][j]+ai, dp[i][j|key])
    for j in range(2**n):
        dp[i][j] = min(dp[i-1][j], dp[i][j])

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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7


n,m=MI()
data=[]
for i in range(m):
    a,b=MI()
    c=LI()
    u=0
    for x in c:
        u+=2**(x-1)
    data.append([a,u])
data.sort()

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

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

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

Solution (Python):
n,m=map(int,input().split())
a,c=[],[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  c.append(sum((1<<(int(i)-1)) for i in input().split()))
inf=float('inf')
dp=[inf]*(1<<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])
print(dp[-1] if inf!=dp[-1] else-1)

Solution (Python):
n,m=map(int,input().split())
dp=[]
INF=10**9
for i in range(m+1):
  dp.append([])
  dp[-1].append(0)
  for j in range(2**n-1):
    dp[-1].append(INF)
keys=[]
for i in range(m):
  a,b=map(int,input().split())
  r=['0']*n
  c=list(map(int,input().split()))
  for j in range(b):
    r[c[j]-1]='1'
  s=''.join(r)
  keys.append([int(s,2),a])
    
for i in range(m):
  for j in range(2**n):
    dp[i+1][j|keys[i][0]]=min(dp[i+1][j|keys[i][0]],dp[i][j]+keys[i][1])
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
if dp[m][2**n-1]==10**9:
  print(-1)
else:
  print(dp[m][2**n-1])

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

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

K = []
for _ in [0]*M:
    a, b = map(int, input().split())
    *C, = map(int, input().split())
    h = 0
    for c in C:
        h ^= 1 << (c-1)
    
    for i in range(1<<N):
        nxt = i|h
        dp[nxt] = min(dp[nxt], dp[i]+a)

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

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

N, M = map(int, input().split())
v = []
t = []

for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    v.append(a)
    ti = 0
    
    for i in range(b):
        ti += 1<<(c[i]-1)
    
    t.append(ti)

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

for S in range(1<<N):
    for i in range(M):
        dp[S|t[i]] = min(dp[S|t[i]], dp[S]+v[i])

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

Solution (Python):
N,M=map(int,input().split())
INF=10**18
dp=[INF]*(1<<N)
dp[0]=0
cost=[None]*M
target=[0]*M

for i in range(M):
    cost[i],b=map(int,input().split())
    
    c=[int(x) for x in input().split()]
    for j in c:
        target[i]=target[i]|(1<<(j-1))
    
for s in range(1<<N):
    for i in range(M):
        ns=s|target[i]
        dp[ns]=min(dp[ns],dp[s]+cost[i])
if dp[-1]==INF:
    print(-1)
else :
    print(dp[-1])

Solution (Python):
INF = 10**10

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

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



DP = [[INF for i in range(0,pow(2,N),1)] for j in range(0,M+1,1)]
for i in range(0,M+1,1):
    DP[i][0]=0 

for i in range(0,M,1):
    cost,openable = key[i+1][0],key[i+1][1]


    for j in range(0,pow(2,N),1):
        if DP[i][j]!=INF:
            DP[i+1][j | openable] = min(DP[i+1][j | openable],DP[i][j]+cost) 
            DP[i+1][j] = min(DP[i+1][j],DP[i][j]) 

print(DP[M][pow(2,N)-1] if DP[M][pow(2,N)-1]!=INF else -1)

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

def main():
  n, m = map(int, input().split())
  U = 2**n
  dp = [ [float("inf")]*(2**n) for _ in range(m) ]
  dp[0][0] = 0
  for i in range(1, m):
    a, b = map(int, input().split())
    k = map(int, input().split())
    c = 0
    for l in k:
      c |= 1<<(l-1)
    for j in range(U):
      dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

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

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

def main():
  n, m = map(int, input().split())
  U = 2**n
  dp = [ [float("inf")]*(2**n) for _ in range(m) ]
  dp[0][0] = 0
  for i in range(1, m):
    a, b = map(int, input().split())
    k = map(int, input().split())
    c = 0
    for l in k:
      c |= 1<<(l-1)
    for j in range(U):
      dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

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

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

N,M = map(int,readline().split())
keys = [None] * M
for i in range(M):
  cost,b = map(int,readline().split())
  bit = 0
  target = list(map(int,readline().split()))
  for t in target:
    bit += (1 << (t - 1))
  keys[i] = (cost, bit)
    

INF = 10 ** 8 + 1
dp = [INF for i in range(2 ** N)]
dp[0] = 0
for key in keys:
  cost, bit = key
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    if dp[j | bit] > dp[j] + cost:
      dp[j | bit] = dp[j] + cost

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