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

n,k,l=map(int,input().split())
def maketree(n,k):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            road[pidx]=road[pidx]|road[qidx]
            for j in road[qidx]:
                roadidx[j]=pidx
            road.pop(qidx)
    return roadidx

def renew(idx):
    count=0
    for i in range(len(idx)):
        if idx[i]==-1:
            idx[i]-=count
            count+=1
    return idx
roadidx=renew(maketree(n,k))
metroidx=renew(maketree(n,l))


idx=[]
for i in range(n):
    idx.append((roadidx[i],metroidx[i]))
res=''
for i in range(n):
    res=res+str(idx.count(idx[i]))+' '
print(res)
###https://img.atcoder.jp/arc065/editorial.pdf

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])
### BUGGY CODE ###

from heapq import heappush, heappop, heapify
import math
def solve():
	n , k= map(int, input().strip().split())
	a= [(-int(x),1,int(x)) for x in input().strip().split()]
	heapify(a)
	for i in range(k):
		x,cnt,orig = heappop(a)
		if x == -1:
			return 1
		heappush(a,(-((orig+cnt)//(cnt+1)),cnt+1,orig))
	return -(heappop(a)[0])


print(solve())

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import math
def check(a,mid,k):
	cnt = 0
	for x in a:
		cur_cnt = (x+mid-1)//mid - 1
		cnt+=cur_cnt
		if cnt > k:
			return False
	return True

def solve():
	n , k= map(int, input().strip().split())
	a= [int(x) for x in input().strip().split()]
	l = 0
	r = 10**9+20
	while r-l > 1:
		mid = (r+l)//2
		if check(a,mid,k):
			r = mid
		else:
			l = mid
	return l+1
 
print(solve())
### BUGGY CODE ###

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

for i in sorted(A):
    res = A.index(i)
    ans.append(res+1)
print(' '.join(map(str, ans)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N

for i, a in enumerate(A):
    ans[int(a-1)] = str(i+1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

money  = [1000,5000,10000]
n,k = list(map(int,input().split()))

def calc_num(n,y):
    for i in range(n+1):
        for j in range((n+1)-i):
            for k in range((n+1)-(i+j)):
                if money[0]*i + money[1]*j + money[2]*k == y and i+j+k == n:
                    return[i,j,k]
    return[-1,-1,-1]

o = calc_num(n,k)[::-1]
print(o[0],o[1],o[2])
                

### FIXED CODE ###

money  = [1000,5000,10000]
n,k = list(map(int,input().split()))

def calc_num(n,y):
    for i in range(n+1):
        for j in range((n+1)-i):
            if money[0]*i + money[1]*j + money[2]*(n-(i+j)) == y and i+j+(n-(i+j)) == n:
                return[n-(i+j),j,i]
    return[-1,-1,-1]

o = calc_num(n,k)
print(o[0],o[1],o[2])
### BUGGY CODE ###

n = int( raw_input() )
A = map( int , raw_input().strip().split(' ') )
q = int( raw_input() )
mi = map( int , raw_input().strip().split(' ') )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n:
    return False
  else:
    res = solve( i+1 , m ) | solve( i+1 , m-A[i] )
    return res

for m in mi:
  if solve( 0 , m ):
    print 'yes'
  else:
    print 'no'
   

### FIXED CODE ###

n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n or m > sum(A):
    return False

  res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
  return res

for m in mi:
  if solve( 0 , m ): print "yes"
  else: print "no"
### BUGGY CODE ###

from collections import Counter

N = int(input())

s = []
check = []
ans = 0
# for x in range(N):
#     for c in input():
#         s[x].append(c)

for _ in range(N):
    check.append(Counter(input()))

while check:
    cc = check.pop(0)
    ans += check.count(cc)


print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())

# check = []
# ans = {}
# answer = 0
# for _ in range(N):
#     s = Counter(input())
#     if s not in check:
#         check.append(s)
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] = 0
#
#     else:
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] += 1
#         answer += ans[str(sorted(s.items(), key=lambda x:x[0]))]
#
# print(answer)

ans = {}
answer = 0
for _ in range(N):
    s = "".join(sorted(input()))

    if s not in ans:
        ans[s] = 0

    else:
        ans[s] += 1
        answer += ans[s]

print(answer)
### BUGGY CODE ###

import sys
NK = input().split()
N,K = int(NK[0]),int(NK[1])
H = list(map(int,input().split()))
if K != 0 and len(H) < K:
    print(0)
    exit()
for i in range(K):
    H.remove(max(H))
print(sum(H))

def input():
    return sys.stdin.readline()[:-1]


### FIXED CODE ###

import sys
NK = input().split()
N,K = int(NK[0]),int(NK[1])
H = list(map(int,input().split()))
if K != 0 and len(H) < K:
    print(0)
    exit()
H.sort()
for i in range(K):
    H.pop(-1)
print(sum(H))

def input():
    return sys.stdin.readline()[:-1]
### BUGGY CODE ###


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

    ans = 0
    a = 0
    b = 0
    for _ in range(N + 1):
        if (a < A) and (b == 0):
            ans += 1
            a += 1
        elif (a == A) and (b == 0):
            a = 0
            b += 1
        elif b < B:
            b += 1
        elif b == B:
            b = 0
    print(ans)
    return 0
if __name__ == '__main__':
    main()

### FIXED CODE ###

N, A, B = map(int, input().split())
ans = N // (A + B) * A
rem = N % (A + B)
ans += min(rem, A)
print(ans)
### BUGGY CODE ###

import bisect
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = [0,0]
max = 0
i = n-1
if n == 2:
	ans[0] = a[1]
	ans[1] = a[0]
else:
	while i > (9999*n//10000-1):
		if a[i]%2 == 0:
			temp = n-1
			while a[i]//2 < a[temp]:
				temp += -1
			
			if a[i] > a[temp-1]:
				if (a[i]//2-a[temp-1]) <= (a[temp+1]-a[i]//2):
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp-1])*math.factorial(a[temp-1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp-1]
				else:
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp+1])*math.factorial(a[temp+1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp+1]
		else:
			temp1 = n-1
			temp2 = n-1
	
			while (a[i]+1)//2 < a[temp1]:
				temp1 += -1
			while (a[i]-1)//2 < a[temp2]:
				temp2 += -1
			
			if a[i] > a[temp1-1]:
				if (a[i]//2-a[temp1-1]) <= (a[temp1+1]-a[i]//2):
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp1-1])*math.factorial(a[temp1-1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp1-1]
				else:
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp1+1])*math.factorial(a[temp1+1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp1+1]
		
			if a[i] > a[temp2-1]:
				if (a[i]//2-a[temp2-1]) <= (a[temp2+1]-a[i]//2):
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp2-1])*math.factorial(a[temp2-1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp2-1]
				else:
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp2+1])*math.factorial(a[temp2+1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp2+1]
		i += -1
print(ans[0],ans[1])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mxm = max(a)
div = []
for i in range(n):
    div.append(abs(mxm/2.0-a[i]))
mini = min(div)
ind = div.index(mini)

if n == 2:
    print(max(a),min(a))
else:
    print(mxm,a[ind])
### BUGGY CODE ###

def add2(l):
    ys = []
    for i in range(len(l)):
        ys += [l[i] + x for x in l[i+1:]]
    return ys


def add(n, l):
    if not l:
        return []
    elif n == 1:
        return l
    elif n == 2:
        return add2(l)
    else:
        ys = [x for x in add(n, l[1:])]
        ys += [l[0] + x for x in add(n-1, l[1:])]
        return ys


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]
    tot = sum(xs)

    if n == 1:
        count = len(list(filter(lambda x: x == a, xs)))
    else:
        count = 0
        lop = n // 2 + 1
        for i in range(1, n//2+1):
            ys = add(i, xs)
            count += len(list(filter(lambda x: x == a * i, ys)))
            if n - i > i:
                zs = list(map(lambda x: tot - x, ys))
                count += len(list(filter(lambda x: x == a * (n - i), zs)))
        if sum(xs) == n * a:
            count += 1

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x = max(xy[i][0],xy[j][0],xy[k][0])
            min_x = min(xy[i][0],xy[j][0],xy[k][0])
            max_y = max(xy[i][1],xy[j][1],xy[k][1])
            min_y = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(xy[i][0],xy[j][0],xy[k][0],xy[l][0])
                min_x = min(xy[i][0],xy[j][0],xy[k][0],xy[l][0])
                max_y = max(xy[i][1],xy[j][1],xy[k][1],xy[l][1])
                min_y = min(xy[i][1],xy[j][1],xy[k][1],xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

### FIXED CODE ###

n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x_old = max(xy[i][0],xy[j][0],xy[k][0])
            min_x_old = min(xy[i][0],xy[j][0],xy[k][0])
            max_y_old = max(xy[i][1],xy[j][1],xy[k][1])
            min_y_old = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x_old-min_x_old)*abs(max_y_old-min_y_old))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max_x_old,xy[l][0])
                min_x = min(min_x_old,xy[l][0])
                max_y = max(max_y_old,xy[l][1])
                min_y = min(min_y_old,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)
### BUGGY CODE ###

def isPrime(n):
    if n == 1:
        return False
    elif n == 2 or n == 3:
        return True
    else:
        for i in range(2, n//2+1):
            if n % i == 0:
                return False
        return True


N = int(input())
count = 0
for _ in range(N):
    if isPrime(int(input())):
        count += 1
print(count)




### FIXED CODE ###

f=lambda x: 1 if x == 2 or x == 3 or (x>3 and x&1==1 and pow(2, x-1, x)==1) else 0
print(sum(f(int(input())) for _ in range(int(input()))))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())

mod = int(10 ** 9 + 7)


def comb(n, k):
    if n - (k - 1) < 1:
        return 0
    res = 1
    for i in range(k):
        res *= n - i
    for i in range(k):
        res //= k - i
    return res

for i in range(1, k + 1):
    print(comb(k - 1, i - 1) * comb(n - k + 1, i) % mod)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())

mod = int(10 ** 9 + 7)


def comb(n, k):
    res = 1
    for i in range(k):
        res *= n - i
    for i in range(k):
        res //= k - i
    return res

for i in range(1, k + 1):
    if i > n - k + 1:
        print(0)
    else:
        print(comb(k - 1, i - 1) * comb(n - k + 1, i) % mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
from collections import defaultdict

n = int(input())
e = [[] for i in range(n)]
for i in range(1,n):
    x = int(input())
    e[x-1].append(i)
num = {}
def dfs(x):
    if x in num:
        return num[x]
    count = len(e[x])
    if count == 0:
        return 0
    d = defaultdict(int)
    ma = 0
    for nex in e[x]:
        v = dfs(nex)
        d[v] += 1
        ma = max(ma,v)
    now = count
    bef = 0
    for v in range(ma,-1,-1):
        if d[v] > 0:
            bef += d[v]
            now = max(now,bef+v)
    num[x] = now
    return now

print(dfs(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
from collections import defaultdict

n = int(input())
e = [[] for i in range(n)]
for i in range(1,n):
    x = int(input())
    e[x-1].append(i)

def dfs(x):

    count = len(e[x])
    if count == 0:
        return 0
    d = defaultdict(int)
    ma = 0
    s = set()
    for nex in e[x]:
        v = dfs(nex)
        d[v] += 1
        s.add(v)
        ma = max(ma,v)
    now = count
    bef = 0
    for v in sorted(list(s),reverse=True):
        bef += d[v]
        now = max(now,bef+v)
    return now

print(dfs(0))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
print(*[A.count(n+1) for n in range(N)],sep="\n")

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = N*[0]

for a in A:
  B[a-1]+=1

print(*B,sep="\n")
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    A = [list(input()) for i in range(H)]
    right = [[0] * W for _ in range(H)]
    left = [[0] * W for _ in range(H)]
    upper = [[0] * W for _ in range(H)]
    under = [[0] * W for _ in range(H)]

    num_max_loc = 0

    for i in range(H):
        tmp_num = 0
        for j in range(W):
            if A[i][j] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                left[i][j] = tmp_num

    for i in range(H):
        tmp_num = 0
        for j in range(W-1, -1, -1):
            if A[i][j] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                right[i][j] = tmp_num

    for i in range(W):
        tmp_num = 0
        for j in range(H):
            if A[j][i] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                upper[j][i] = tmp_num

    for i in range(W):
        tmp_num = 0
        for j in range(H-1, -1, -1):
            if A[j][i] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                under[j][i] = tmp_num

    for i in range(H):
        for j in range(W):
            tmp_sum = (
                left[i][j] + right[i][j] + upper[i][j] + under[i][j] - 3)
            num_max_loc = max(num_max_loc, tmp_sum)

    print(num_max_loc)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    A = [list(input()) for i in range(H)]
    right = [[0] * W for _ in range(H)]
    left = [[0] * W for _ in range(H)]
    upper = [[0] * W for _ in range(H)]
    under = [[0] * W for _ in range(H)]

    num_max_loc = 0

    for i in range(H):
        tmp_num = 0
        for j in range(W):
            if A[i][j] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                left[i][j] = tmp_num

    for i in range(H):
        tmp_num = 0
        for j in range(W-1, -1, -1):
            if A[i][j] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                right[i][j] = tmp_num

    for i in range(W):
        tmp_num = 0
        for j in range(H):
            if A[j][i] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                upper[j][i] = tmp_num

    for i in range(W):
        tmp_num = 0
        for j in range(H-1, -1, -1):
            if A[j][i] == "#":
                tmp_num = 0
            else:
                tmp_num += 1
                under[j][i] = tmp_num

    for i in range(H):
        for j in range(W):
            tmp_sum = (
                left[i][j] + right[i][j] + upper[i][j] + under[i][j] - 3)
            num_max_loc = max(num_max_loc, tmp_sum)

    print(num_max_loc)


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

s = list(input())
q = int(input())
for i in range(q):
  d = input()
  if d == '1':
    s.reverse()
  else:
    a, b, c = list(d.split())
    b = int(b)
    if b == 1:
      s.insert(0, c)
    else:
      s.append(c)
print(*s,sep='')

### FIXED CODE ###

s = list(input())
q = int(input())
judge = 1
front = []
back = []
for i in range(q):
  a = list(map(str,input().split()))
  if int(a[0]) == 1:
    judge *= -1
  else:   
    if (int(a[1]) == 1 and judge == 1) or (int(a[1]) == 2 and judge == -1):
      front.append(a[2])
    else:
      back.append(a[2])
ans = front[::-1] + s + back
if judge == -1:
  ans.reverse()
print(*ans, sep='')
### BUGGY CODE ###

from collections import deque

N, M, K = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
C = [0]*K
D = [0]*K
for i in range(K):
    C[i], D[i] = map(int,input().split())

friend = {i: set([]) for i in range(1, N+1)}
brock = {i: set([]) for i in range(1, N+1)}
for i in range(M):
    friend[A[i]].add(B[i])
    friend[B[i]].add(A[i])
for i in range(K):
    brock[C[i]].add(D[i])
    brock[D[i]].add(C[i])

labels = [0] * (N+1)


def mark(n, label):
    if labels[n] != 0:
        return -1
    else:
        q = deque()
        q.append(n)
        labels[n] = label
        while q != deque():
            node = q.pop()
            labels[node] = label
            for i in friend[node]:
                if labels[i] == 0:
                    q.append(i)
        return label


label = 1
for n in range(1, N + 1):
    if mark(n, label) != -1:
        label += 1

group_size = [0] * label
for l in range(1, len(group_size)):
    group_size[l] = labels.count(l)

res = [0] * N
for n in range(1, N + 1):
    tmp = 0
    for b in brock[n]:
        if labels[n] == labels[b]:
            tmp += 1
    res[n - 1] = group_size[labels[n]] - 1 - len(friend[n]) - tmp

print(*res)

### FIXED CODE ###

from collections import deque
from collections import Counter
N, M, K = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
C = [0]*K
D = [0]*K
for i in range(K):
    C[i], D[i] = map(int,input().split())

friend = {i: set([]) for i in range(1, N+1)}
brock = {i: set([]) for i in range(1, N+1)}
for i in range(M):
    friend[A[i]].add(B[i])
    friend[B[i]].add(A[i])
for i in range(K):
    brock[C[i]].add(D[i])
    brock[D[i]].add(C[i])

labels = [0] * (N+1)


def mark(n, label):
    if labels[n] != 0:
        return -1
    else:
        q = deque()
        q.append(n)
        labels[n] = label
        while q != deque():
            node = q.pop()
            labels[node] = label
            for i in friend[node]:
                if labels[i] == 0:
                    q.append(i)
        return label


label = 1
for n in range(1, N + 1):
    if mark(n, label) != -1:
        label += 1

group_size = Counter(labels)

res = [0] * N
for n in range(1, N + 1):
    tmp = 0
    for b in brock[n]:
        if labels[n] == labels[b]:
            tmp += 1
    res[n - 1] = group_size[labels[n]] - 1 - len(friend[n]) - tmp

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

N,Ma,Mb=map(int,input().split())
Med=[]
for i in range(N):
  a=[int(x) for x in input().split()]
  Med.append(a)
  
#[i]まででMa=[j],Mb=[k]を作る場合の最小のコストdp
#dp[i+1][j+Ma][k+Mb]=min(dp[i][j+Ma][k+Mb],dp[i][j][k]+Cost)
#リストをinfで初期化。inf=作れない配合なので、continue。初期値はdp[0][0][0]=0
dp=[[[float('inf') for j in range(401)] for k in range(401)] for i in range(N+1)]
dp[0][0][0]=0

for i in range(N):
  for j in range(401):
    for k in range(401):
      if dp[i][j][k]==float('inf'):
        continue
      dp[i+1][j][k]=min(dp[i][j][k],dp[i+1][j][k])
      dp[i+1][j+Med[i][0]][k+Med[i][1]]=min(dp[i][j+Med[i][0]][k+Med[i][1]],dp[i][j][k]+Med[i][2])

ans=float('inf')
for i in range(1,N+1):
  if i*Ma<401 and i*Mb<401:
    ans=min(ans,dp[N][i*Ma][i*Mb])
if ans==float('inf'):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N,Ma,Mb=map(int,input().split())
Med=[]
cnt_a=0
cnt_b=0
for i in range(N):
  a=[int(x) for x in input().split()]
  Med.append(a)
  cnt_a+=a[0]
  cnt_b+=a[1]
R=max(cnt_a,cnt_b)
#[i]まででMa=[j],Mb=[k]を作る場合の最小のコストdp
#dp[i+1][j+Ma][k+Mb]=min(dp[i][j+Ma][k+Mb],dp[i][j][k]+Cost)
#リストをinfで初期化。inf=作れない配合なので、continue。初期値はdp[0][0][0]=0
dp=[[[float('inf') for j in range(R+1)] for k in range(R+1)] for i in range(N+1)]
dp[0][0][0]=0

for i in range(N):
  for j in range(R+1):
    for k in range(R+1):
      if dp[i][j][k]==float('inf'):
        continue
      dp[i+1][j][k]=min(dp[i][j][k],dp[i+1][j][k])
      dp[i+1][j+Med[i][0]][k+Med[i][1]]=min(dp[i][j+Med[i][0]][k+Med[i][1]],dp[i][j][k]+Med[i][2])

ans=float('inf')
for i in range(1,N+1):
  if i*Ma<R+1 and i*Mb<R+1:
    ans=min(ans,dp[N][i*Ma][i*Mb])
if ans==float('inf'):
  print(-1)
else:
  print(ans)