Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict
import sys

people = defaultdict(set)

n, _ = map(int, next(sys.stdin).strip().split())

for i, line in enumerate(sys.stdin):
    _, *langs = line.strip().split()
    new = {i}
    for lang in langs:
        old = people[lang]
        new.update(old)
        for l in people.keys():
            if people[l] is old:
                people[l] = new

if len(next(people.values())) == n:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import sys

next(sys.stdin)

_, *langs = map(int, next(sys.stdin).strip().split())
common_langs = set(langs)

unreachable = list()
for line in sys.stdin:
    _, *langs = map(int, line.strip().split())
    unreachable.append(set(langs))

change = True
while change:
    change = False
    for langs in unreachable:
        if len(common_langs & langs) > 0:
            s = len(common_langs)
            common_langs.update(langs)
            change |= not s == len(common_langs)
            langs.clear()
    unreachable = list(langs for langs in unreachable if len(langs) > 0)

if len(unreachable) == 0:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = list(map(int, input().split()))
    c = sorted(list(map(int, input().split())))
    count = 0

    # See:
    # https://img.atcoder.jp/arc084/editorial.pdf
    # https://docs.python.jp/3/library/bisect.html
    from bisect import bisect_left
    from bisect import bisect_right

    for number in b:
        high = bisect_left(a, number)
        low = bisect_right(c, number)
        count += len(a[:high]) * len(c[low:])

    print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = list(map(int, input().split()))
    c = sorted(list(map(int, input().split())))
    count = 0

    # See:
    # https://img.atcoder.jp/arc084/editorial.pdf
    # https://docs.python.jp/3/library/bisect.html
    # https://beta.atcoder.jp/contests/abc077/submissions/1740764
    from bisect import bisect_left
    from bisect import bisect_right

    for number in b:
        a_count = bisect_left(a, number)
        c_count = n - bisect_right(c, number)
        count += a_count * c_count

    print(count)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N + 200 : break
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

A,B,N=map(int,input().split())
M=0
if B<N:
	C=B
else:
	C=N
for i in range(C+1):
	x=int(A*i/B)
	y=int(i/B)
	z=x-A*y
	if M<z:
		M=z
print(M)

### FIXED CODE ###

A,B,N=map(int,input().split())
if B==N:
	C=B-1
elif B<N:
	C=B-1
else:
	C=N
x=int(A*C/B)
y=int(C/B)
z=x-A*y
print(z)
### BUGGY CODE ###

input()
words = [int(x) for x in input().split(" ")]
save = []
for w in words:
  if w in save:
    print("NO")
    exit()
  save.append(w)
print("YES")

### FIXED CODE ###

len1 = int(input())
len2 = len(set(input().split(" ")))
if len1 == len2:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
dic = defaultdict(int)
for i in range(n):
    dic[a[i]]+=1
Q= int(input())
for q in range(Q):
    b, c = map(int, input().split())
    dic[c]+=dic[b]
    dic[b]=0
    ans = 0
    for j in dic:
        ans += dic[j]*j
    print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
dic = defaultdict(int)
for i in range(n):
    dic[a[i]]+=1
ans = 0
for j in dic:
    ans += dic[j]*j

Q= int(input())
for q in range(Q):
    b, c = map(int, input().split())
    s= dic[b]*(c-b)
    ans += s
    
    dic[c]+=dic[b]
    dic[b]=0
    
    print(ans)
### BUGGY CODE ###

n = int(input())
sn = []
set_sn = []
dic_sn = [{} for i in range(n)]
cnt = 0
sn = [input() for i in range(n)]
set_sn = [set(sn[i]) for i in range(n)]
dic_sn = [{si: sn[i].count(si) for si in set_sn[i]} for i in range(n)]

for i in range(n):
    for j in range(i + 1, n):
        if dic_sn[i] == dic_sn[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
dic_sorted_s = {}
count = 0
for i in range(n):
    s = input()
    str_sorted_s = ''.join(sorted(s))
    try:
        count += dic_sorted_s[str_sorted_s]
        dic_sorted_s[str_sorted_s] += 1
    except KeyError:
        dic_sorted_s[str_sorted_s] = 1
print(count)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
a=0
for i in range(max(0,n-k)):
    a+=min(l)
    l.remove(min(l))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
a=0
for i in range(max(0,n-k)):
    a+=l[i]
print(a)
### BUGGY CODE ###

a,b,k=map(int,input().split())

for n in range(a,b+1):
    if n<a+k or b-k<n:
        print(n)


### FIXED CODE ###

a,b,k=map(int,input().split())

if a+k>b-k:
    for n in range(a,b+1):
        print(n)
else:
    for n in range(a,a+k):
        print(n)
    for n in range(b-k+1,b+1):
        print(n)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from fractions import gcd


def lcm(a, b):
    return a * b / gcd(a, b)


MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

l = 1
for a in A:
    l = lcm(l, a)

l %= MOD

ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD) % MOD
    ans %= MOD

print(int(ans))


### FIXED CODE ###

from fractions import gcd

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))

lcm = 1
for s in A:
    lcm = s * lcm // gcd(lcm, s)

ans = lcm * sum([pow(s, mod - 2, mod) for s in A]) % mod

print(int(ans % mod))
### BUGGY CODE ###

N = str(input())
Lines = input().split(" ")
LinesInt = []
answer = 0

for line in Lines:
    line = int(line)
    LinesInt.append(line)

for lineI in range(len(LinesInt)):
    for lineJ in range(lineI+1,len(LinesInt)):
        for lineK in range(lineJ+1,len(LinesInt)):
             if (LinesInt[lineI] + LinesInt[lineJ] > LinesInt[lineK]) and (LinesInt[lineK] + LinesInt[lineJ] > LinesInt[lineI]) and (LinesInt[lineK] + LinesInt[lineI] > LinesInt[lineJ]):
                answer += 1
print(answer)



### FIXED CODE ###

N = int(input())
Lines = list(map(int, input().split(" ")))
Lines.sort()
answer = 0
 
import bisect
 
for lineI in range(N):
    for lineJ in range(lineI+1,N):
    	answer += bisect.bisect_left(Lines,Lines[lineI]+Lines[lineJ])-lineJ-1
print(answer)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
s = 0
c = 1
while max(A) != 0:
    #print(max(A))
    s0 = 0
    s1 = 0
    for i,j in enumerate(A):
        A[i],mod = divmod(j,2)
        if mod==1:
            s1 +=1
        else:
            s0 +=1
    s = (s+(s0*s1*c)%(10**9+7))%(10**9+7)
    c *= 2
print(s)

### FIXED CODE ###

import numpy as np
from math import ceil,log2
N = int(input())
a = np.array(list(map(int,input().split())),dtype=np.int64)
ans = 0
count = 1
if max(a) == 0:
    x = 1
else:
    x = ceil(log2(max(a)))

for i in range(x):
    b = a%2
    s = np.count_nonzero(b==1)*np.count_nonzero(b==0)*count
    ans +=s
    count *= 2
    a = a//2
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

s = 0
for i in range(n-1):
    for j in range(i+1, n):
        s += (a[i] * a[j])
        s %= (10**9 + 7)

print(s)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

s = 0
ss = 0
for i in range(n):
    j = n - i - 1
    s += (a[j] * ss % (10**9 + 7))
    s %= (10**9 + 7)
    ss += a[j]

print(s)
### BUGGY CODE ###

A, B, C, K = map(int,input().split())

L = []
for x in range(0,A):
	L.append(1)
for y in range(0,B):
	L.append(0)
for z in range(0,C):
	L.append(-1)
print(sum(L[0:K]))


### FIXED CODE ###

A, B, C, K = map(int,input().split())
# 1 2 3 4
card = K#4
# 取れるカードの数
result = 0
# 得点は0
if card < A: # 4 < 1 false
	print(card)
	# Aのカードを取るだけで済むパターン
else:
	card -= A # 4 - 1
	# print("カード残り",card)
	# Aのカードを取り切ってもまだとれるカードの数
	if card < B:
		print(A)
	else:
		card -= B # 3 - 2
		#print("カード残り", card)
		x = card * -1
		#print("X",x)
		print(A+x)
### BUGGY CODE ###

s = input()
n = int(input())

for i in range(n):
    q = list(input().split())
    if q[0] == '1':
        s = s[::-1]
    else:
        if q[1] == '1':
            s = q[2]+s
        else:
            s = s+q[2]
print(s)


### FIXED CODE ###

from collections import deque
s = deque(input())
n = int(input())
now: bool = True

for i in range(n):
    q = list(input().split())
    if q[0] == '1':
        now = not now
    else:
        if (q[1] == '1' and now == True) or (q[1] == '2' and now == False):
            s.appendleft(q[2])
        elif (q[1] == '1' and now == False) or (q[1] == '2' and now == True):
            s.append(q[2])
if now == True:
    print(''.join(s))
else:
    print(''.join(reversed(s)))
### BUGGY CODE ###

from math import floor
A,B,N = map(int,input().split())
ans = 0
if B-1 <=  N:
  for x in range(B-1,N+1,B):
    ans = max(ans, floor(A*x/B) - A*floor(x/B))
else:
  ans = floor((A*N)/B) - A*floor(N/B)
print(ans)

### FIXED CODE ###

from math import floor
A,B,N = map(int,input().split())
ans = 0
if B <=  N:
  ans = floor(A*(B-1)/B) - A*floor((B-1)/B)
else:
  ans = floor((A*N)/B) - A*floor(N/B)
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = {start}
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = min(open, key=lambda x: w[x])
        open.remove(target)
        for next in E[target]:
            if not next in w:
                open.add(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))


### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = deque([start])
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.popleft()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


n, m = map(int, readline().split())
if is_prime(m) and n != 1:
    print(1)
    exit()
for i in range(m // n, 0, -1):
    if m % i == 0:
        print(i)
        exit()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


n, m = map(int, readline().split())
if is_prime(m):
    if n == 1:
        print(m)
    else:
        print(1)
    exit()
for i in range(m // n, 0, -1):
    if m % i == 0:
        print(i)
        exit()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

H,W = map(int, input().split())

a = set()
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            a.add(i)
        i += 1
#print(a)

m = 0
for i in range(H*W):
    ni = H+W-2
    if i in a:
        ni = 0
    else:
        for j in a:
            ni = min(ni, abs(j//W-i//W) + abs(j%W -i%W))
            if ni == 1:
                break
#            print(ni, abs(j-i)//W, abs(j%W -i%W))
    m = max(m, ni)
print(m)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
index = []
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        index.append(i + 1)
for i in range(Q):
    l, r = map(int, input().split())
    print(len([i for i in index if l <= i < r]))


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
t = [0] * (N+1)
cnt = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        cnt += 1
    t[i] = cnt
t[-1] = t[-2]
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

def counting_sort(A, B, n, k=10000):
    C = [0 for i in range(k+1)]
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, k+1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = list(map(int , input().split()))

B = [0 for i in range(n)]
for k in A:
    counting_sort(A, B, n)

print(*B)

### FIXED CODE ###

import array
import sys
def counting_sort(A, B, n, k=10000):
    C = array.array('I', [0 for i in range(k+1)])
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, k+1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = list(map(int , sys.stdin.readline()[:-1].split()))

B = array.array("I", [0 for i in range(n)])
counting_sort(A, B, n)

print(*B)
### BUGGY CODE ###

import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = []
for i in range(len(L)):
  L_cum.append(sum(L[0:i+1]))
L_cum.append(0)

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[]
    for i in range(num_0-K+1):
      rev.append(L_cum[2*(K+i)]-L_cum[i*2-1])
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[]
    for i in range(num_0-K+1):
      rev.append(L_cum[2*(K+i)+1]-L_cum[2*i])
    ans=max(rev)
print(ans)

### FIXED CODE ###

import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = [0]*(len(L)+1)
for i in range(len(L)):
  L_cum[i]=L_cum[i-1]+L[i]

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)]-L_cum[i*2-1]
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)+1]-L_cum[2*i]
    ans=max(rev)
print(ans)
### BUGGY CODE ###

m_d = list()    # 魔法移動距離
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界を壁で囲む
S = ['##{}##'.format(s_row) for s_row in s]
S = ['##{}##'.format('#' * (w+4))]*2 + S
S = S + ['##{}##'.format('#' * (w+4))]*2

# BFS探索用キュー
from collections import deque
q_a = deque() # 徒歩
q_b = deque() # ワープ

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q_a.append([si,sj])

while (len(q_a)>0):
    i, j = ij = q_a.popleft()
    q_b.append(ij)
    d = dist[i][j]
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q_a.append([ni,nj])

    if len(q_a) == 0:
        while (len(q_b)>0):
            i, j = q_b.popleft()
            d = dist[i][j]
            for di, dj in m_d:
                ni, nj = di+i, dj+j
                if (S[ni][nj]=='#'):
                    continue # 壁
                if (dist[ni][nj]<=d):
                    continue # 探索済みコスト以上
                dist[ni][nj] = d+1
                q_a.append([ni,nj])

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

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)
        if minc==-1:
            continue
        ret=min(ret,a+minc)
    
    if ret==10**10:
        dp[current]=-1
        return -1
    
    dp[current]=ret
    return ret

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

### FIXED CODE ###

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