Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(100000000)


def process():
    data = []
    for line in get_data():
        line = line.split()
        if len(line) == 2:
            if line[0] == line[1] == '0':
                data = []
                continue
            H = int(line[0])
            W = int(line[1])
        elif len(line) == 0:
            pass
        else:
            data.append(line[0])
            if len(data) == H:
                field = create_field(H, W)
                print search(H, W, data, field)


def search(H, W, data, field):
    count = 0
    for i in xrange(H):
        for j in xrange(W):
            if field[i][j] == 0:
                continue
            _search(i, j, H, W, data[i][j], data, field)
            count += 1
    return count


def _search(i, j, H, W, cell, data, field):
    field[i][j] = 0
    for a in xrange(i-1, i+2):
        if -1 < a < H:
            pass
        else:
            continue
        for b in xrange(j-1, j+2):
            if -1 < b < W:
                pass
            else:
                continue

            if a != i and b != j:
                continue

            if field[a][b] == 0:
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data, field)
    return


def create_field(H, W):
    field = []
    for i in xrange(H):
        raw = []
        for j in xrange(W):
            raw.append(1)
        field.append(raw)
    return field


def get_data():
    return [line.strip() for line in raw_input()]


process()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)


def main():
    solve()


def solve():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if not -1 < a < H:
            continue
        for b in xrange(j-1, j+2):
            if not -1 < b < W:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue

            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()
4 5

### FIXED CODE ###

H, W = map(int, input().split())
w = W//2
h = H//2
lh = H - h
lw = W- w

if H < 2 or W < 2:
    print(1)
else:
    print(lh * lw + w * h)
from collections import deque
str_l = ["dream", "dreamer", "erase" ,"eraser"]
s = input()
n = len(s)

deque = deque()
deque.append(0)

def str_plus(i):
    s1 = s[i]
    if s1 == "d":
        if s[i:i+5] == "dream":
            if s[i+5:i+7] == "er":
                return [i+5,i+7]
            else:
                return [i+5]
        else:
            return False
    if s1 == "e":
        if s[i:i+5] == "erase":
            if s[i+5] == "r":
                return [i+5,i+6]
            else:
                return [i+5]
        else:
            return False

ans = "NO"

while deque:
    i = deque.pop()
    if i == n:
        ans = "YES"
        break
    l = str_plus(i)
    if l != False and l != None:
        deque.extend(l)

print(ans)

### FIXED CODE ###

s = input()[::-1]
l = [ 'dream', 'dreamer', 'erase', 'eraser']
for i in range(4):
	s1 = l[i][::-1]
	l[i] = s1

n = len(s)
i = 0
t = tuple(l)

while i < n:
	judge = 0
	s_l = []
	for j in (5,6,7):
		if n-i >= j:
			s1 = s[i:i+j]
			if s1 in t:
				i += j
				judge = 1
	
	if judge == 0:
		break

if i == n:
	print('YES')
else:
	print('NO')
def main():
	N = int(input())
	A = list(map(int, input().split()))
	while(len(A) != 1):
		A.sort()
		mini = A[0]
		for i in range(1, len(A)):
			if i >= len(A):
				continue
			if A[i] % mini == 0:
				A.pop(i)
			else:
				A[i] = A[i] % mini
		A = QUICKSORT(A)
		piv = A[0]
		for i in range(1, len(A)):
			if i >= len(A):
				continue
			if A[i] == piv:
				A.pop(i)
	print(A[0])

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	while(len(A) != 1):
		A.sort()
		mini = A[0]
		i = 1
		while(True):
			if A[i] % mini == 0:
				A.pop(i)
			else:
				A[i] = A[i] % mini
				i += 1
			if i == len(A):
				break
		A = list(set(A))
	print(A[0])

if __name__ == '__main__':
	main()
S = sorted(input())
test = sorted('abcdefghijklmnopqrstuvwxyz')
for num in range(len(S)):
    if num == 26:
        ans ='None'
        break
    if S[num] != test[num]:
        ans = num
        break
print('None' if ans=='None' else test[num] )

### FIXED CODE ###

S = sorted(list(set(list(input()))))
test = sorted('abcdefghijklmnopqrstuvwxyz')
ans = -1
if S == test:
    print('None')

elif S[-1] == test[len(S)-1]:
    print(test[len(S)])

else:
    for num in range(len(S)):
        if test[num] != S[num]:
            print(test[num])
            break
N, M, X = map(int, input().split(' '))
gates = [int(input()) for i in range(M)]

can = [len([i for i in gates if i > X]), len([i for i in gates if i < X])]

print(min(can))

### FIXED CODE ###

N, M, X = map(int, input().split(' '))
gates = map(int, input().split(' '))

c1 = len([i for i in gates if i < X])
can = [c1, M - c1]

print(min(can))
from math import log, ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa == a:
            ret += cur
        else:
            b = a >> cur
            if pa >= b:
                cur = ceil(log(pa / b, 4)) * 2
                ret += cur
                # print(pa, a, d, cur, ret)
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m2
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
if N == M:
  print("Yes")
if N != M:
  print("No")

### FIXED CODE ###

N,M = map(int,input().split())
if N == M:
  print("Yes")
else:
  print("No")
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros((N+1,13),dtype=np.int)
    dp[0,0]=1

    for i in range(N):
        if S[i]=="?":
            for s in range(10):
                for j in range(13):
                    dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                    dp[i+1][(s*(10**i)+j) % 13] %= MOD
        else:
            s=int(S[i])
            for j in range(13):
                dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                dp[i+1][(s*(10**i)+j) % 13] %= MOD

    res = dp[N,5]
    print(res%MOD)

if __name__ == '__main__':
    main()


### FIXED CODE ###

A,B=map(int,input().split())
if (A+B)%2 == 0:
    print(int((A+B)/2))
else:
    print("IMPOSSIBLE")
s=list(input())
if s.count('K')==1 and s.count('I')==1 and s.count('H')==1 ands.count('B')==1 ands.count('R')==1:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import copy
s=list(input())
if len(s)>=10 or len(s)<=3:
    print('NO')
else:
    n=len(s)
    cnt=''.join(s)
    ans=[cnt]
    for i in range(2**(n+1)):
        c=copy.deepcopy(s)
        cc=0
        #print(c)
        for j in range(n+1):
            if (i >> j) & 1:
                c.insert(j+cc,'A')
                cc+=1
        cnt=''.join(c)
        ans.append(cnt)
    if 'AKIHABARA'in ans:
        print('YES')
    else:
        print('NO')
    #print(ans)
S = input()
a = len(S)
if S[:(a - 1) / 2] == S[(a + 1) / 2:]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

S = input()
n = len(S)
a = S[:int((n - 1) / 2)]
b = S[int((n + 1) / 2):]
if a == b:
    print("Yes")
else:
    print("No")
def euclid(a, b):
    r = a % b
    if 0 == r:
        return b
    return max(1, euclid(b, r))


def greatest_common_divisor(a, b):
    return int(a * b / euclid(a, b))


def greatest_common_divisor_arr(arr):
    if 1 == n:
        return arr[0]
    else:
        d = greatest_common_divisor(arr[0], arr[1])
        for i in range(2, n):
            d = greatest_common_divisor(d, arr[i])
        return d


n = int(input())
ans = greatest_common_divisor_arr([int(input()) for _ in range(n)])
print(min(ans, 10 ** 18))


### FIXED CODE ###


def gcd(a, b):
    if 0 == b:
        return a
    return gcd(b, a % b)


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


def lcm_arr(arr):
    ans = arr[0]
    for i in range(1, n):
        ans = lcm(ans, arr[i])
    return ans


n = int(input())
ans = lcm_arr([int(input()) for _ in range(n)])
print(min(ans, 10 ** 18))
import sys
sys.setrecursionlimit(10**5)

n,m,k = map(int, input().split())

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

group_ID = 0
for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        f_search(i, group_ID)
    group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n,m,k = map(int, input().split())

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]
group_ID = 0

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        f_search(i, group_ID)
        group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])
N,K = map(int,input().split())
A = list(map(int,input().split()))
A_unique = list(set(A))
N_unique = len(A_unique)

a_sort = sorted([A.count(A_unique[i]) for i in range(N_unique))])

M = A_unique-K
if M <= 0:
	print(0)
	exit()

ans = 0
for i in range(0,M):
	ans += a_sort[i]
print(ans)

### FIXED CODE ###

str = input()
list = list(str)

print(int(list[0])+int(list[1])+int(list[2]))
class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(N)
used_list = [False] * N

reward = 0
for b, a in ab_list:
	index = M - a
#	print("i", index, a)
	prev_index = None
	while True:
		if not used_list[index]:
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1
		
#	print(index)
	if index >= 0:
		used_list[index] = True
		reward += b

print(reward)


### FIXED CODE ###

class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(M)
used_list = [False] * M

reward = 0
for b, a in ab_list:
	index = M - a
	prev_index = None
	while index >= 0:
#		print(index, M, a, N)
		if not used_list[index]:
			used_list[index] = True
			reward += b
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1

print(reward)
N, K = map(int, input().split())
P = list(map(int, input().split()))
numbers = [0,1,2,3,4,5,6,7,8,9]
use = []
for i in numbers:
  if not i in P:
    use.append(i)

ul = []
for u5 in [0, use[1]]:
  for u4 in use:
    for u3 in use:
      for u2 in use:
        for u1 in use:
          ul.append(u5*10000 + u4*1000 + u3*100 + u2*10 + u1)
ul.sort()
for r in ul:
  if N <= r:
    print(r)
    break

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
numbers = [0,1,2,3,4,5,6,7,8,9]
use = []
for i in numbers:
  if not i in P:
    use.append(i)

ul = []
if 0 in use:
  for u5 in [0,use[1]]:
    for u4 in use:
      for u3 in use:
        for u2 in use:
          for u1 in use:
            ul.append(u5*10000 + u4*1000 + u3*100 + u2*10 + u1)
else:
    for u4 in use:
      for u3 in use:
        for u2 in use:
          for u1 in use:
            ul.append(use[0]*10000 + u4*1000 + u3*100 + u2*10 + u1)
            ul.append(u4*1000 + u3*100 + u2*10 + u1)
            ul.append(u3*100 + u2*10 + u1)
            ul.append(u2*10 + u1)
            ul.append(u1)
ul.sort()
for r in ul:
  if N <= r:
    print(r)
    break
import fractions
import functools
import sys

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
for i in xrange(N):
    B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))

### FIXED CODE ###

import fractions
import functools
import sys

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
from collections import  Counter
N = int(input())
votes = [input() for i in range(N)]
count = dict(Counter(votes))
max_vote = max(count.values())
res = []
for i in count:
    if count[i] == max_vote:
        res.append(i)
        continue
res.sort()
for i in res:
    print(i)

### FIXED CODE ###

A, B, C = map(int, input().split())
if A == B and A == C:
    print("No")
elif A == B or A == C or B == C:
    print("Yes")
else:
    print("No")
n, q = map(int,input().split())
s = list(input())
x = []

ans = 0
for i in range(n):
	if s[i] == "A" and s[i+1] == "C":
		ans += 1
		x.append(ans)
	else:
		x.append(ans)

for j in range(q):
	l, r = map(int,input().split())
	print(x[r-1]-x[l-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0]
t=0

for i in range(0,n-1):
    if s[i]=="A" and s[i+1]=="C":
        t+=1
        c.append(t)
    else:
        c.append(t)

for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])
b = input()
if b == "A":
    print("T")
elif b == "T":
    print("A")
else b == "G":
    print("C")
else:
    print("G")

### FIXED CODE ###

b = input()
L = [["A","T"],["C","G"]]
for i in range(2):
    if b in L[i]:
        if L[i][0] == b:
            print(L[i][1])
        else:
            print(L[i][0])
X, Y, Z, K = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

max_k_list = [0] * (X * Y * Z)
i = 0
for a_i in range(X):
    for b_i in range(Y):
        for c_i in range(Z):
            if (a_i + 1) * (b_i + 1) * (c_i + 1) <= K:
                max_k_list[i] = a_list[a_i] + b_list[b_i] + c_list[c_i]
                i += 1

max_k_list.sort(reverse = True)
[print(k) for k in max_k_list[:K]]


### FIXED CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

heap = []
heapq.heappush(heap, (-(a_list[0] + b_list[0] + c_list[0]), 0, 0, 0))
searched = []
result = [0] * K

for k in range(K):
    elem = heapq.heappop(heap)
    result[k] = - elem[0]

    if elem[1] + 1 <= X - 1:
        a_next = (-(a_list[elem[1] + 1] + b_list[elem[2]] + c_list[elem[3]]), elem[1] + 1, elem[2], elem[3])
        if not a_next in searched:
            heapq.heappush(heap, a_next)
            searched.append(a_next)

    if elem[2] + 1 <= Y - 1:
        b_next = (-(a_list[elem[1]] + b_list[elem[2] + 1] + c_list[elem[3]]), elem[1], elem[2] + 1, elem[3])
        if not b_next in searched:
            heapq.heappush(heap, b_next)
            searched.append(b_next)

    if elem[3] + 1 <= Z - 1:
        c_next = (-(a_list[elem[1]] + b_list[elem[2]] + c_list[elem[3] + 1]), elem[1], elem[2], elem[3] + 1)
        if not c_next in searched:
            heapq.heappush(heap, c_next)
            searched.append(c_next)

[print(k) for k in result]
letters = eval(input("Enter: "))
if letters.index(2)==letters.index(3) and letters.index(4)==letters.index(5):
  print("Yes)
elif letters=="coffee-like":
  print("Yes")
else:
   print("No")

### FIXED CODE ###

l = input()
print("Yes" if (l[2]==l[3] and l[4]==l[5]) else "No")
import numpy as np

if __name__=="__main__":
    inputs_number  = lambda : [int(x) for x in input().split()]
    N, Ma, Mb = inputs_number()
    drugs = [inputs_number() for i in range(N)]
    inf = 100*N + 1
    dp = np.ones((N+1,N*10+1,N*10+1)) * inf
    dp[0,0,0] = 0.0
    for i in range(N):
	for ca in range(N*10+1):
            for cb in range(N*10+1):
		if(dp[i,ca,cb]==inf):
                    continue
                dp[i+1,ca,cb]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]])
                dp[i+1,ca+drugs[i][0],cb+drugs[i][1]]=np.min([dp[i+1,ca+drugs[i][0],cb+drugs[i][1]],dp[i,ca,cb]+drugs[i][2]])
    print(-1)
    ans = inf
    for ca in range(1, N*10+1):
        for cb in range(1, N*10+1):
	    if(Ma*cb==Mb*ca and dp[N,ca,cb]<ans):
            	ans = dp[N,ca,cb]
    if(ans==inf):
	ans = -1
    #print(int(ans))


### FIXED CODE ###

import numpy as np
import copy

if __name__=="__main__":
    inputs_number  = lambda : [int(x) for x in input().split()]
    N, Ma, Mb = inputs_number()
    drugs = [inputs_number() for i in range(N)]
    inf = 100*N + 1
    dp = np.ones((2,N*10+1,N*10+1)).astype(np.int32) * inf
    dp = dp.tolist()
    dp[0][0][0] = 0.0

    for i in range(N):
        for ca in range(10*i+1):
            for cb in range(10*i+1):
                if(dp[0][ca][cb]==inf):
                    continue
                dp[1][ca][cb]=min([dp[1][ca][cb], dp[0][ca][cb]])
                dp[1][ca+drugs[i][0]][cb+drugs[i][1]]=min([dp[1][ca+drugs[i][0]][cb+drugs[i][1]], dp[0][ca][cb]+drugs[i][2]])
        dp[0] = copy.copy(dp[1])
        dp[1] = (np.ones((N*10+1,N*10+1)).astype(np.int32) * inf).tolist()
    ans = inf
    for ca in range(1, N*10+1):
        for cb in range(1, N*10+1):
            if(Ma*cb==Mb*ca and dp[0][ca][cb]<ans):
                ans = dp[0][ca][cb]
    if(ans==inf):
        ans = -1
    print(int(ans))