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

x, y = map(int, input().split())
z = x
while z < 10**18:
    if z % y != 0:
        print(z)
        exit()
    z += x
print(-1)

### FIXED CODE ###

x, y = map(int, input().split())
if x % y == 0:
    print(-1)
else:
    print(x)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if abs(i-j) == a[i]+a[j]:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
ans = 0
l=[]
for i in range(n):
    l.append(i-a[i])
cnt = Counter(l)
for i in range(n):
    ans += cnt[i+a[i]]

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

# -*- coding: utf-8 -*-
#Python
import sys

N=input()
a=[[] for i in range(N+1)]

for i in range(N-1):
    u,v=list(map(int,raw_input().split()))
    a[u].append(v)
    a[v].append(u)

#print a

#初期化
kyori=(N+1)*[0]

sys.setrecursionlimit(1000000)
#深さ優先探索
def dfs(Graph, Start, Visited=None):
	if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
	Visited.append(Start)  #現在の頂点を探索済みリストに加える
	#print(Start, "\n", Visited)  #現在の頂点と探索済みリストを表示
	for Next in Graph[Start]:  #次に探索する頂点の候補
		#print "Next::"+str(Next)
		if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
		kyori[Next]=kyori[Start]+1
		dfs(Graph, Next, Visited)  #再帰
	return kyori


kyori_from_start=dfs(a,1)


kyori=(N+1)*[0]
dfs(a,N)




f_p=0
s_p=0
for k in range(1,N+1):
	if kyori_from_start[k]<=kyori[k]:
		f_p+=1
	else:
		s_p+=1

#print f_p
#print s_p

if f_p>s_p:
	print 'Fennec'
else:
	print 'Snuke'


### FIXED CODE ###

# -*- coding: utf-8 -*-
#Python
import sys

N=input()
adj=[[] for i in range(N+1)]

#隣接リスト
for i in range(N-1):
    x,y=list(map(int,raw_input().split()))
    adj[x].append(y)
    adj[y].append(x)

#print adj

#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist=(N+1)*[0]


#先頭から深さ優先探索
S.append(1)
while len(S) != 0:
	#print S
	v=S.pop()
	#print v
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				dist[u]=dist[v]+1
				#print S

#print dist



#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist2=(N+1)*[0]

#最後から深さ優先探索
S.append(N)
while len(S) != 0:
	#print S
	v=S.pop()
	#print v
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				dist2[u]=dist2[v]+1
				#print S

#print dist2



f_p=0
s_p=0
for k in range(1,N+1):
	if dist[k]<=dist2[k]:
		f_p+=1
	else:
		s_p+=1


if f_p>s_p:
	print 'Fennec'
else:
	print 'Snuke'
### BUGGY CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] >= 0 or S[h][w] == '#': continue
    dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

colors = [
    [R, G, B],
    [R, B, G],
    [G, R, B],
    [G, B, R],
    [B, R, G],
    [B, G, R],
]

cand = []
for C1, C2, C3 in colors:
    for c1 in C1:
        for c2 in C2:
            if c1 > c2:
                continue
            for c3 in C3:
                if c2 > c3:
                    continue
                if c1 > c3:
                    continue
                cand.append((c1,c2,c3))

ans = 0
for c1, c2, c3 in cand:
    if c2 - c1 != c3 - c2:
        ans += 1

print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt * g_cnt * b_cnt

for i in range(N):
    for dist in range(N):
        j = i + dist
        k = j + dist
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1

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

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

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num))

if __name__ == '__main__':

    n = int(input())
    T = HashTable(n*30)
    C = [input().split(" ") for i in range(n)]
    C = map(lambda x:(x[0], getNum(x[1])), C)
    
    for command, num in C:
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

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

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

import sys
if sys.version_info.minor < 5:
    from fractions import gcd
else:
    from math import gcd
import math

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

ans = [1]
for i in range(2, gcd(A, B)+1):
    # print("i: {}".format(i))

    if A % i == 0 and B % i == 0:
        # print("This is a cd of A and B.")
        ans.append(i)

    while A % i == 0:
        A /= i
    while B % i == 0:
        B /= i

# print(set(ans))

print(len(set(ans)))


### FIXED CODE ###

import sys
if sys.version_info.minor < 5:
    from fractions import gcd
else:
    from math import gcd
import math

DEBUG = False

A, B = map(int, input().split())
g = gcd(A, B)
if DEBUG:
    print("gcd(A, B): {}".format(g))

ans = [1]
i= 2
temp = g
while i <= int(-(-g**0.5//1))+1:
    if DEBUG:
        print("i: {}, g: {}".format(i, g))

    if temp % i == 0:
        if DEBUG:
            print("This is a cd of A and B.")
        ans.append(i)

    while temp % i == 0:
        temp //= i

    i += 1

if temp != 1:
    ans.append(temp)

if DEBUG:
    print(ans)

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

#python3
import collections as col
n=int(input())
a=[input() for i in range(n)]

b=col.defaultdict(int)
for i in a:
  b[''.join(sorted(i))]+=1


c = [''.join(sorted(a)) for _ in range(n)]
#print(sum2)

sum1=0
for i in b.values():
  sum1+=i*(i-1)//2
print(sum1)







### FIXED CODE ###

#python3
n = int(input())
s = [str(input()) for _ in range(n)]
sep = ''
dic = dict()
for string in s:
  tmp = sep.join(sorted(string))
  if tmp in dic:
    dic[tmp] += 1 
  else :
    dic[tmp] = 1
ans = 0
for i in dic.values(): 
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
n, k = map(int, readline().split())


graph = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
ans = 1

kaidan = [0] * (k + 1)
kaidan[0] = 1
for i in range(1, k + 1):
    kaidan[i] = i * kaidan[i - 1]


def perm(k, i):
    if i > k:
        return 0
    return kaidan[k] // kaidan[k - i]


# dfs

stack = [1]
used = [False] * (n + 1)
while stack:
    v = stack.pop()
    used[v] = True
    if v == 1:
        ans *= k * perm(k - 1, cnt[v])
        ans %= mod
    else:
        ans *= perm(k - 2, cnt[v] - 1)
        ans %= mod
    for u in graph[v]:
        if used[u] == True:
            continue
        stack.append(u)

print(ans)


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, readline().split())


graph = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
ans = 1

mod = 10 ** 9 + 7
kaidan = [1] * (10 ** 5 + 1)
gyaku = [1] * (10 ** 5 + 1)

for i in range(1, 10 ** 5 + 1):
    kaidan[i] = i * kaidan[i - 1] % mod
    gyaku[i] = pow(kaidan[i], mod - 2, mod)


def perm(k, i):
    if i > k:
        return 0
    return kaidan[k] * gyaku[k - i]


# dfs

stack = [1]
used = [False] * (n + 1)
while stack:
    v = stack.pop()
    used[v] = True
    if v == 1:
        ans *= k * perm(k - 1, cnt[v])
        ans %= mod
    else:
        ans *= perm(k - 2, cnt[v] - 1)
        ans %= mod
    for u in graph[v]:
        if used[u] == True:
            continue
        stack.append(u)

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

A,B,C,K = (int(x) for x in input().split())
s = 0
for i in range(K):
    if A != 0:
        s += 1
        A -= 1
    elif A == 0 and B != 0:
        s = s
        B -= 1
    elif A == 0 and B == 0:
        s -= 1
print(s)


### FIXED CODE ###

A,B,C,K = (int(x) for x in input().split())
s = 0
d = (2*(10**10))
while True:
    if A <= K:
        s += (1*A)
        K = K - A
        A = d
    elif A != d and A > K:
        s = 1*K
        break
    elif A == d and B <= K:
        s = s
        K = K - B
        B = d
    elif A == d and  B != d and B > K:
        pass
        break
    elif A == d and B == d and C <= K:
        s -= (1*C)
        C = d
        break
    elif A == d and B == d and C != d and C > K:
        s -= (1*K)
        break
print(s)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
for _ in range(q):
    l,r = map(int, input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n-1):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

N = int(input())
S = list(map(int, list(input())))

def f(a):
    i = 0
    for j in range(N):
        if S[j] == a[i]:
            i += 1
            if i > 2:
                return True
    return False

res = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            if f((i, j, k)):
                res += 1

print(res)

### FIXED CODE ###

N = int(input())
S = list(map(int, list(input())))

def f(a):
    i = 0
    for j in range(N):
        if S[j] == a[i]:
            i += 1
            if i > 2:
                return True
    return False

res = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            if f((i, j, k)):
                res += 1

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

import sys
from itertools import permutations, combinations, combinations_with_replacement, product

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())
K_ = K
comb = list(combinations(A, 2))
for i, p in enumerate(comb):
    comb[i] = (min(p), max(p))
comb = sorted(comb, key=lambda p: p[0] * p[1])

tmp = comb[K - 1]
print(tmp[0] * tmp[1])


### FIXED CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def count(x):
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += N * len(neg) - np.searchsorted(A, -(-x // neg), side='left').sum()
    cnt -= np.count_nonzero(A * A <= x)

    return cnt // 2


N, K, *A = map(int, read().split())
A = np.array(A)
A.sort()

neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

r = 10**18
l = -r

while r - l > 1:
    m = (r + l) // 2
    if count(m) >= K:
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

import sys
N = int(input())
array = list(map(int,input().split()))

if not ( 2 <= N <= 10**5 ): sys.exit()
if not ( 0 <= min(array) and max(array) <= 10**18): sys.exit()

sum = array[0]
for I in range(1,len(array)):
    sum *= array[I]
print(sum) if sum <= 10**18 else print(-1)

### FIXED CODE ###

import sys
N = int(input())
array = list(map(int,input().split()))

if not ( 2 <= N <= 10**5 ): sys.exit()
if not ( 0 <= min(array) and max(array) <= 10**18): sys.exit()
if 0 in array: print(0); sys.exit()

sum = array[0]
for I in range(1,len(array)):
    sum *= array[I]
    if sum > 10**18: print(-1);sys.exit()
print(sum)
### BUGGY CODE ###

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


### FIXED CODE ###

X= int(input())
val = X // 100
diff = X % 100
if diff <= 5*val:
    print(1)
else:
    print(0)
### BUGGY CODE ###

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

mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

for i in range(2, N+1):
  g1.append((g1[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod//i)) % mod)
  g2.append((g2[-1] * inv[-1]) % mod)

#def cmb(n, r):
#  if r < 0 or r > n:
#    return 0
#  r = min(r, n-r)
#  return g1[n] * g2[r] * g2[n-r]

ans = 0
for x in range(N+1):
  rest = K - A*x
  if rest >= 0 and rest % B == 0:
    y = rest // B
    for g in range(max(0, x+y-N), min(x,y)+1):
      r = x - g
      b = y - g
      ans += g1[N] * g2[r] * g2[g] * g2[b] * g2[N-r-g-b] % mod
      #ans += cmb(N,r) * cmb(N-r,g) * cmb(N-r-g, b) % mod

print(ans % mod)

### FIXED CODE ###

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

MOD = 998244353
factorials = [1]
inv_facts = [1]
for i in range(1, N+1):
    factorials.append(factorials[-1] * i % MOD)
    inv_facts.append(inv_facts[-1] * pow(i, MOD-2, MOD) % MOD)

def combi(n, k):
    ret = factorials[n]
    ret *= inv_facts[k]
    ret %= MOD
    ret *= inv_facts[n-k]
    ret %= MOD
    return ret

ans = 0
for a in range(N+1):
    rest = K - (A * a)
    if rest < 0:
        break
    if rest % B == 0:
        b = rest // B
        if b <= N:
            tmp = combi(N, a) * combi(N, b) % MOD
            ans += tmp
            ans %= MOD
print(ans)
### BUGGY CODE ###

#coding:utf-8

n = int(input())

a = input().split()

count = 0

r = [(n - int(m)) for n,m in enumerate(a)]
l = [(n + int(m)) for n,m in enumerate(a)]

r.remove(r[0])
l.remove(l[-1])

mar = max(r)
mir = min(r)
mal = max(l)
mil = min(l)

R = {i:0 for i in range(mir,mar + 1)}
L = {i:0 for i in range(mil,mal + 1)}

for n,m in zip(r,l):
    R[n] += 1
    L[m] += 1

for i in range(max(mir,mil),min(mar,mal)+1):
    count += R[i] * L[i]

print("{}".format(count))

### FIXED CODE ###

#coding:utf-8

n = int(input())

a = input().split()

count = 0

r = [(n - int(m)) for n,m in enumerate(a)]
l = [(n + int(m)) for n,m in enumerate(a)]

r.remove(r[0])
l.remove(l[-1])

mar = max(r)
mir = min(r)
mal = max(l)
mil = min(l)

R = {}
L = {}

for n,m in zip(r,l):
    R[n] = 0
    L[m] = 0

for n,m in zip(r,l):
    R[n] += 1
    L[m] += 1

for i in R.keys():
    if i in L.keys():
        count += R[i] * L[i]

print("{}".format(count))
### BUGGY CODE ###

tmp = input()
N = int(tmp.split()[0])
M = int(tmp.split()[1])
A = []
B = []
for i in range(N):
	tmp = input()
	A.append(int(tmp.split()[0]))
	B.append(int(tmp.split()[1]))

cnt=0
total=0
while cnt < M:
	mini = N
	minv = 999999999999999
	for i in range(N):
		if minv > A[i]:
			minv = A[i]
			mini = i
	cnt += B[mini]
	total += A[mini]*B[mini]
	A[mini] = 9999999999999999
total -= minv*(cnt-M)
print(total)

### FIXED CODE ###

tmp = input()
N = int(tmp.split()[0])
M = int(tmp.split()[1])
AB = []
for i in range(N):
	tmp = input()
	AB.append([int(tmp.split()[0]),int(tmp.split()[1])])

AB.sort()

cnt=0
total=0
i = 0
while cnt < M:
	cnt += AB[i][1]
	total += AB[i][0]*AB[i][1]
	i+=1
total -=  AB[i-1][0]*(cnt-M)
print(total)
### BUGGY CODE ###

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

    graph = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        if a not in graph: graph[a] = [b]
        else: graph[a].append(b)
        # if b not in graph: graph[b] = [a]
        # else: graph[b].append(a)

    ops = dict()
    for i in range(Q):
        p, x = map(int, input().split())
        if p not in ops: ops[p] = x
        else: ops[p] += x

    # print(graph)
    # print(ops)
    vals = [0 for _ in range(N)]
    v = 0
    if 1 in ops: v = ops[1]
    cur = [[1, v]]

    while cur:
        temp = []
        for a, v in cur:
            vals[a-1] += v
            if a in graph:
                for b in graph[a]:
                    if b in ops:
                        temp.append([b, v+ops[b]])
                    else:
                        temp.append([b, v])
        cur = temp

    print(' '.join(map(str, vals)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

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

    graph = collections.defaultdict(list)
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a].append(b)

    ops = collections.defaultdict(int)
    for i in range(Q):
        p, x = map(int, input().split())
        ops[p] += x

    vals = [0 for _ in range(N)]
    v = 0
    if 1 in ops: v = ops[1]
    cur = [[1, v]]

    while cur:
        temp = []
        for a, v in cur:
            vals[a-1] += v
            for b in graph[a]:
                temp.append([b, v+ops[b]])
        cur = temp

    print(' '.join(map(str, vals)))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    cost = [INF] * (2 << N)
    used = [False for i in range(M)]
    end = (1 << N) - 1
    
    def dfs(state):
        if state == end:
            return
        for i in range(M):
            ns = state | C[i]
            if not used[i] and state < ns:
                new_cost = cost[state] + A[i]
                if new_cost < cost[ns]:
                    cost[ns] = new_cost
                    used[i] = True
                    dfs(ns)
                    used[i] = False
        return cost

    cost[0] = 0
    dfs(0)
    return cost[end] if cost[end] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    # dp[state][i]: i本の鍵[0, i)を使って状態stateにするための最小コスト
    n_states = 1 << N
    end_state = n_states - 1
    dp = [[INF for j in range(2)] for state in range(n_states)]
    dp[0][0] = 0
    dp[0][1] = 0

    for j in range(M):
        m0 = j & 1
        m1 = 1 - m0
        for state in range(n_states):
            next_state = state | C[j]
            dp[state][m1] = min(dp[state][m1], dp[state][m0])
            if next_state > state:
                dp[next_state][m1] = min(dp[next_state][m1], dp[state][m0] + A[j])
    
    m0 = M & 1
    return dp[end_state][m0] if dp[end_state][m0] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))