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

from collections import deque

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
CH -= 1
CW -= 1
DH -= 1
DW -= 1

mp = [input() for _ in range(H)]
ds = [[0,-1],[0,1],[-1,0],[1,0]]

memo1 = [[0]*W for _ in range(H)]

c = 0
for i in range(H):
  for j in range(W):
    if memo1[i][j] != 0:
      continue
    if mp[i][j] == '#':
      memo1[i][j] = -1
      continue
    h = deque([(i,j)])
    c += 1
    memo1[i][j] = c
    while h:
      t = h.popleft()
      for d in ds:
        if t[0]+d[0] >= 0 and t[0]+d[0] < H \
           and t[1]+d[1] >= 0 and t[1]+d[1] < W:
          if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo1[t[0]+d[0]][t[1]+d[1]] == 0:
            memo1[t[0]+d[0]][t[1]+d[1]] = c
            h.append((t[0]+d[0], t[1]+d[1]))
    
if memo1[CH][CW] == memo1[DH][DW]:
  print(0)
  exit()
    
ds = [[i,j] for i in range(-1,2) for j in range(-1,2)]
dic = {i:set([]) for i in range(1,c+1)}

for i in range(H):
  for j in range(W):
    if memo1[i][j] == -1:
      s = set([])
      for d in ds:
        if i+d[0] >= 0 and i+d[0] < H and j+d[1] >= 0 and j+d[1] < W:
          if memo1[i+d[0]][j+d[1]] > 0 and memo1[i+d[0]][j+d[1]] not in s:
            for u in s:
              dic[memo1[i+d[0]][j+d[1]]].add(u)
              dic[u].add(memo1[i+d[0]][j+d[1]])
            s.add(memo1[i+d[0]][j+d[1]])

s = memo1[CH][CW]
t = memo1[DH][DW]
  
lst = [10**9]*(c+1)
lst[s] = 0

h = deque([(s,0)])
while h:
  u = h.popleft()
  for v in dic[u[0]]:
    if lst[v] <= u[1]:
      continue
    lst[v] = lst[u[0]] + 1
    h.append((v,lst[v]))
    
    
if lst[t] == 10**9:
  print(-1)
else:
  print(lst[t])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
CH, CW = map(lambda x:int(x)-1, input().split())
DH, DW = map(lambda x:int(x)-1, input().split())

mp = [input() for _ in range(H)]
ds1 = [[0,-1],[0,1],[-1,0],[1,0]]
ds2 = [[i,j] for i in range(-2,3) for j in range(-2,3)]

memo = [[0]*W for _ in range(H)]
memo[CH][CW] = 1

h1 = deque([(CH,CW)])
h2 = deque([])
ans = 0

while 1:
  while h1:
    t = h1.popleft()
    h2.append(t)
    for d in ds1:
      if t[0]+d[0] >= 0 and t[0]+d[0] < H \
         and t[1]+d[1] >= 0 and t[1]+d[1] < W:
        if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 0:
          memo[t[0]+d[0]][t[1]+d[1]] = 1
          h1.append((t[0]+d[0], t[1]+d[1]))
  if memo[DH][DW] == 1:
    print(ans)
    exit()
  ans += 1

  while h2:
    t = h2.popleft()
    for d in ds2:
      if t[0]+d[0] >= 0 and t[0]+d[0] < H \
         and t[1]+d[1] >= 0 and t[1]+d[1] < W:
        if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 0:
          memo[t[0]+d[0]][t[1]+d[1]] = 1
          h1.append((t[0]+d[0], t[1]+d[1]))
          
  if not h1:
    print(-1)
    exit()
### BUGGY CODE ###

from collections import deque

G = dict()
N, M = map(int, input().split())
color = [0]*(N+1)
for n in range(1, N+1):
    G[n] = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())

for _ in range(Q):
    v, d, c = map(int, input().split())
    # BFS
    dist  = [-1]*(N+1)
    deq = deque([v])
    color[v] = c
    dist[v] = 0
    while len(deq) > 0:
        s = deq.popleft()
        if dist[s] >= d:
            break
        for t in G[s]:
            if dist[t] != -1:
                pass
            else:
                dist[t] = dist[s] + 1
                color[t] = c
                deq.append(t)
                
for n in range(1, N+1):
    print(color[n])
                


### FIXED CODE ###

from collections import deque

G = dict()
N, M = map(int, input().split())
color = [0]*(N+1)
for n in range(1, N+1):
    G[n] = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())




data = [list(map(int, input().split())) for _ in range(Q)]
data.reverse()
color_d = [-1]*(N+1)

for v, d, c in data:
    if color_d[v] >= d:
        pass
    # BFS
    deq = deque([v])
    if color[v] == 0:
        color[v] = c
    color_d[v] = d
    while len(deq) > 0:
        s = deq.popleft()
        for t in G[s]:
            if color_d[t] >= color_d[s] - 1:
                pass
            else:
                color_d[t] = color_d[s] - 1
                if color[t] == 0:
                    color[t] = c
                if color_d[t] > 0:
                    deq.append(t)
                
for n in range(1, N+1):
    print(color[n])
### BUGGY CODE ###

n,m = map(int,input().split())
l,r = [],[]
for i in range(m):
    a,b = map(int,input().split())
    l.append(a)
    r.append(b)
count = 0
for i in range(1,n+1):
    for j in range(m):
        if i < l[j] or i > r[j]:
            count -= 1
            break
print(n + count) 

### FIXED CODE ###

n,m = map(int,input().split())
l,r = [],[]
for i in range(m):
    a,b = map(int,input().split())
    l.append(a)
    r.append(b)
num = list(range(1,n+1))
lmax = max(l)
rmin = min(r)
if lmax > rmin:
    print(0)
else:
    gate = set(range(lmax,rmin+1))
    ans = list(set(num) & gate)
    print(len(ans))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

def main():
    md = 998244353
    s = input()
    n = len(s)
    if s.count(s[0]) == n:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    ord0 = ord("a")
    a = [ord(c) - ord0 for c in s]
    r = sum(a) % 3
    dp = [[[[0] * 3 for _ in range(2)] for _ in range(3)] for _ in range(n)]
    for m in range(3):
        dp[0][m][0][m] = 1
    # print(a)
    # print(dp)
    for i in range(n - 1):
        for j in range(3):
            for k in range(2):
                for m in range(3):
                    pre = dp[i][j][k][m]  # iけた j余り k連続有無 m前の位
                    for nm in range(3):
                        nj = (j + nm) % 3
                        if nm == m:
                            dp[i + 1][nj][1][nm] = (dp[i + 1][nj][1][nm] + pre) % md
                        else:
                            dp[i + 1][nj][k][nm] = (dp[i + 1][nj][k][nm] + pre) % md
    d = 1
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            d = 0
            break
    print((sum(dp[n - 1][r][1]) + d) % md)

main()


### FIXED CODE ###

def main():
    md = 998244353
    s = input()
    n = len(s)
    if s.count(s[0]) == n:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    ord0 = ord("a")
    a = [ord(c) - ord0 for c in s]
    r = sum(a) % 3
    dp = [[[[0] * 3 for _ in range(2)] for _ in range(3)] for _ in range(n)]
    for m in range(3):
        dp[0][m][0][m] = 1
    # print(a)
    # print(dp)
    for i in range(n - 1):
        for j in range(3):
            for k in range(2):
                for m in range(3):
                    pre = dp[i][j][k][m]  # iけた j余り k連続有無 m前の位
                    for nm in range(3):
                        nj = (j + nm) % 3
                        if nm == m:
                            dp[i + 1][nj][1][nm] = (dp[i + 1][nj][1][nm] + pre) % md
                        else:
                            dp[i + 1][nj][k][nm] = (dp[i + 1][nj][k][nm] + pre) % md
    d = 1
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            d = 0
            break
    print((sum(dp[n - 1][r][1]) + d) % md)

main()
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] != S[j]:
            for k in range(j+1, N):
                if j-i != k-j and S[i] != S[k] and S[j] != S[k]:
                    ans += 1
print(ans)

### FIXED CODE ###

import copy
N = int(input())
S = input()

R = set()
G = set()
B = set()

for i in range(N):
    if S[i] == "R":
        R.add(i)
    elif S[i] == "G":
        G.add(i)
    else:
        B.add(i)

ans = len(R)*len(G)*len(B)

for r in R:
    for g in G:
        L = g - r
        if g + L in B:
            ans -= 1
        if r - L in B:
            ans -= 1
        if L % 2 == 0 and L//2 + r in B:
            ans -= 1
            



print(ans)
### BUGGY CODE ###

import collections

#def bfs(tree, s, distance):
#    queue = [s]
#    distance[s] = 0
#
#    while queue:
#        v = queue.pop(0)
#        for node, cost in tree[v]:
#            if distance[node] == -1:
#                distance[node] = distance[v] + cost
#                queue.append(node)

N = int(input())

Tree = collections.defaultdict(list)

for i in range(N - 1):
    a, b, c = map(int, input().split())
    Tree[a].append((b, c))
    Tree[b].append((a, c))

q, k = map(int, input().split())

distance = collections.defaultdict(lambda : -1)
#bfs(Tree, k, distance)
queue = [k]
distance[k] = 0
while queue:
    v = queue.pop(0)
    for node, cost in Tree[v]:
        if distance[node] == -1:
            distance[node] = distance[v] + cost
            queue.append(node)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x] + distance[y])


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(int(1e7))

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

for i in range(N - 1):
    a, b, c = map(int, input().split())
    Tree[a].append((b, c))
    Tree[b].append((a, c))

q, k = map(int, input().split())

depth = {}
dfs(k, -1, 0)

for i in range(q):
    x, y = map(int, input().split())
    print(depth[x] + depth[y])
### BUGGY CODE ###

n=int(input())
o=list(i for i in range(1,n+1))
for j in o:
    if j%5==0:
        o.remove(j)
for p in o:
    if p%3==0:
        o.remove(p)
print(sum(o))


### FIXED CODE ###

n=int(input())
l=[]
o=list(i for i in range(1,n+1))
for j in o:
    if j%5 ==0 or j%3 ==0:
        l.append(j)
print(sum(o)-sum(l))
### BUGGY CODE ###

S=input()
Q=int(input())
for _ in range(Q):
    target = input()
    if target == '1':
        S=S[::-1]
    else:
        a,b,c=target.split()
        if b=='1':
            S=c+S
        else:
            S=S+c
print(S)

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
r='1'
for _ in range(Q):
    target = input()
    if target == '1':
        if r=='1':
            r='2'
        else:
            r='1'
    else:
        a,b,c=target.split()
        if b=='1' and r=='1':
            S.appendleft(c)
        elif b=='2' and r=='1':
            S.append(c)
        elif b=='1' and r=='2':
            S.append(c)
        else:
            S.appendleft(c)
if r=='2':
    S.reverse()
print(''.join(list(S)))
### BUGGY CODE ###

N = int(input())
people = list(map(int, input().split()))
order = [people.index(i)+1 for i in range(1, N+1)]
print(" ".join(map(str, order)))

### FIXED CODE ###

N = int(input())
people = list(map(int, input().split()))
out_list = [0]*N
for i in range(N):
    out_list[people[i]-1] = i + 1
print(" ".join(map(str, out_list)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h,w = l_in()
S = []
for _ in range(h):
    s = s_in()
    S.append(s)
    
from collections import deque

res = 0
for i in range(h):
    for j in range(w):
        q = deque()
        s = set()
        check = lambda x,y: (not (x,y) in s) and x >= 0 and x < h and y >=0 and y < w and S[x][y] == '.'
        
        if S[i][j] == '.':
            q.append((i,j,0))

        while len(q) > 0:
            i,j,d = q.popleft()
            s.add((i,j))
            res = max(d,res)
            
            if check(i+1,j):
                q.append((i+1,j,d+1))
            if check(i-1,j):
                q.append((i-1,j,d+1))
            if check(i,j+1):
                q.append((i,j+1,d+1))
            if check(i,j-1):
                q.append((i,j-1,d+1))

print(res)



### FIXED CODE ###

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h,w = l_in()
S = [s_in() for _ in range(h)]
    
from collections import deque

res = 0
for i in range(h):
    for j in range(w):
        q = deque()
        s = set()
        check = lambda x,y: (not (x,y) in s) and x >= 0 and x < h and y >=0 and y < w and S[x][y] == '.'
        
        if S[i][j] == '.':
            q.append((i,j,0))

        while len(q) > 0:
            i,j,d = q.popleft()
            s.add((i,j))
            res = max(d,res)
            
            if check(i+1,j):
                s.add((i+1,j))
                q.append((i+1,j,d+1))
            if check(i-1,j):
                s.add((i-1,j))                
                q.append((i-1,j,d+1))
            if check(i,j+1):
                s.add((i,j+1))            
                q.append((i,j+1,d+1))
            if check(i,j-1):
                s.add((i,j-1))            
                q.append((i,j-1,d+1))

print(res)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for i, j in zip(dy, dx):
        ny = py + i
        nx = px + j

        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx]:
            continue

        que.append([ny, nx])
        reached[ny][nx] += reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        reached[i][j] = 0
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for y, x in zip(dy, dx):
        ny = py + y
        nx = px + x
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx] == -1:        
            que.append([ny, nx])
            reached[ny][nx] = reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)
### BUGGY CODE ###

import bisect
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort()
b.sort()
c.sort()
s=bisect.bisect_left(a,b[-1])
l=bisect.bisect_right(c,b[0])
cnt=0
ab=[]
for B in b:
    for A in a[:s+1]:
        if B>A:
            ab+=[B]
ans=0
for AB in ab:
    for C in c[l:]:
        if AB<C:
            ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=sorted([int(i) for i in input().split()])
b=sorted([int(i) for i in input().split()])
c=sorted([int(i) for i in input().split()])
ans=0
for B in b:
    m=bisect.bisect_left(a,B)
    l=bisect.bisect_right(c,B)
    ans+=m*(n-l)
print(ans)
### BUGGY CODE ###

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j in range(2**n):
        tmp[j] = min(tmp[j], dp[j])
        tmp[j|c] = min(tmp[j|c], dp[j]+a)
    dp = tmp

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


### FIXED CODE ###

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        if d < tmp[j]:
            tmp[j] = d
        if d+a < tmp[j|c]:
            tmp[j|c] = d+a
    dp = tmp

print(dp[-1] if dp[-1]<INF else -1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]

fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    bitset = 1
    for i in range(n):
        if i == mi-1:
            continue
        bitset |= (bitset << a[i])
    needed = False
    j = max(0, k - a[mi-1])
    bitset >>= j
    while j < k:
        if (bitset&1) == 1:
            needed = True
            break
        bitset >>= 1
        j += 1

    if needed:
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

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

for i in range(K):
    if A>0:
        A -= 1
    elif B>0:
        B -= 1

print(A, B, sep=' ')

### FIXED CODE ###

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

if A>=K:
    print(A-K, B)
elif B>=K-A:
    print(0, B-K+A)
else:
    print(0,0)
### BUGGY CODE ###

n=int(input())
ans=1
while ans<=n:
    ans*2
print(ans//2)

### FIXED CODE ###

n=int(input())
ans=1
while ans<=n:
    ans*=2
print(ans//2)
### BUGGY CODE ###

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

d =[]

for i in range(A):
    d.append(1)

for j in range(B):
    d.append(0)

for k in range(C):
    d.append(-1)


d.sort(reverse=True)


KK = 0
for l in range(K):
    N = d[l]
    #print(N)
    KK = KK + N
print(KK)
    


### FIXED CODE ###

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

if A >= K:
    print(K)
    

elif A + B >= K:
    print(A)

elif A + B < K:
    c = -1 * (K-(A+B))
    #print(c)
    #print(A)
    cc = A + c
    print(cc)
### BUGGY CODE ###

x = int(input())
n = x//100 + 1
for i in range(n):
  for j in range(n):
     for k in range(n):
         for l in range(n):
             for m in range(n):
                 for o in range(n):
                    c = 100*i + 101*j + 102*k + 103*l + 104*m + 105*o
                    if c == x:
                      print(1)
                      exit()
print(0)      


### FIXED CODE ###

x = int(input())
n = x//100 + 1
 
for i in range(n):
  for j in range(n):
     for k in range(n):
         for l in range(n):
             for m in range(n):
                 c = 100*i + 101*j + 102*k + 103*l + 104*m
                 if x >= c:
                    t = x-c
                
                    if t%105 == 0:
                        print(1)
                        exit()
                    
print(0)
### BUGGY CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    t,w={},{}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        t[(l,r)]=d
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    #chk=set()
    chk=deque()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        #chk.add((i,0))
        chk.append((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=x[1]+j[1]:
                    #if (x[0],j[0]) in t and t[(i,j[0])]!=
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        t[(i,j[0])]=x[1]+j[1]
                        #chk.add((j[0],x[1]+j[1]))
                        chk.append((j[0],x[1]+j[1]))
                    else:
                        #chk.add((j[0],x[1]+j[1]))
                        chk.append((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()


### FIXED CODE ###

def sol():
    n,m=map(int,input().split())
    t,w={},{}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w: w[l].add((r,d))
        else: w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    chk=set()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        chk.add((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=t[(i,x[0])]+j[1]:
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        #t[(i,j[0])]=t[(i,x[0])]+j[1]
                        t[(i,j[0])]=x[1]+j[1]
                        chk.add((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()
### BUGGY CODE ###

n, m = map(int, input().split())
dp = [[float('inf')] * 2 ** n for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = [int(i_) for i_ in input().split()]
    temp = 0
    for kk in c:
        temp += 1 << (kk - 1)
    for j in range(2 ** n):
        if j == 0:
            dp[i][temp | j] = a
        else:
            dp[i][temp | j] = min(dp[i - 1][j] + a, dp[i][temp | j])
        if (i > 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j])

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

### FIXED CODE ###

n, m = map(int, input().split())
dp = [[float('inf')] * 2 ** n for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = [int(i_) for i_ in input().split()]
    temp = 0
    for kk in c:
        temp += 1 << (kk - 1)
    for j in range(2 ** n):
        if j == 0:
            dp[i][temp | j] = a
        else:
            dp[i][temp | j] = min(dp[i - 1][j] + a, dp[i][temp | j])
        if (i > 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j])

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