CodeEff/ECCO huggingface dataset:
# Original solution
#D問題
NM=40
ABM=10

N,M1,M2=list(map(int,input().split()))
A=[]
B=[]
C=[]
for i in range(N):
    a,b,c=list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)
amax,bmax,cmax,=max(A),max(B),max(C)
dp=[[[N*cmax for broop in range(NM*ABM+1)] for aroop in range(NM*ABM+1)] for nroop in range(NM+1)]
dp[0][0][0]=0
for i in range(N):
    for cb in range(NM*ABM):
        for ca in range(NM*ABM):
            dp[i+1][ca][cb]=min(dp[i+1][ca][cb],dp[i][ca][cb])
            if ca+A[i]<NM*ABM and cb+B[i]<NM*ABM:
                dp[i+1][ca+A[i]][cb+B[i]]=min(dp[i+1][ca+A[i]][cb+B[i]],dp[i][ca][cb]+C[i])

ans=N*cmax
for cb in range(NM*ABM):
    CB=cb+1
    for ca in range(NM*ABM):
        CA=ca+1
        if ca*M2 == cb*M1:
            ans=min(ans,dp[N][CA][CB])

if ans == N*cmax:
    print((-1))
else:
    print(ans)

# Optimized solution
#D問題
NM=40
ABM=10
MM=400

N,M1,M2=list(map(int,input().split()))
A=[]
B=[]
C=[]
for i in range(N):
    a,b,c=list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)
cmax=max(C)
CM=N*cmax+10
dp=[[[CM for broop in range(401)] for aroop in range(401)] for nroop in range(N+1)]
dp[0][0][0]=0
for i in range(N):
    for cb in range(401):
        for ca in range(401):
            if dp[i][ca][cb]==CM:
                continue
            dp[i+1][ca][cb]=min(dp[i+1][ca][cb],dp[i][ca][cb])
            if ca+A[i]<401 and cb+B[i]<401:
                dp[i+1][ca+A[i]][cb+B[i]]=min(dp[i+1][ca+A[i]][cb+B[i]],dp[i][ca][cb]+C[i])

ans=CM
for cb in range(400):
    for ca in range(400):
        CB=cb+1
        CA=ca+1
        if CA*M2 == CB*M1:
            ans=min(ans,dp[N][CA][CB])

if ans == CM:
    print((-1))
else:
    print(ans)
# Original solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, ma, mb = list(map(int, input().split()))
abc = [None]*n
for i in range(n):
    a,b,c = tuple(map(int, input().split()))
    abc[i] = (a*mb - b*ma, c)
abc.sort()
def halfcomb(l):
    n = len(l)
    n1 = n//2
    n2 = (n+1)//2
    l1 = []
    l2 = []
    
    for b in range(1, 1<<n2):
        v11, v12 = 0, 0
        v21, v22 = 0, 0
        for i in range(n2):
            if b&1<<i:
                item = l[n1+i]
                v21+=item[0]
                v22+=item[1]
                if b<(1<<n1) and i<n1:
                    item = l[i]
                    v11+=item[0]
                    v12+=item[1]
        if b<(1<<n1):
            l1.append((v11,v12))
        l2.append((v21,v22))
    return l1, l2
l1, l2 = halfcomb(abc)
d2 = {}
for v,c in l2:
    if v in d2:
        d2[v] = min(d2[v], c)
    else:
        d2[v] = c
ans = float("inf")
for v,c in l1:
    if v==0:
        ans = min(ans, c)
for v,c in l2:
    if v==0:
        ans = min(ans, c)
        
for v,c in l1:
    if -v in d2:
        ans = min(ans, c+d2[-v])
if ans == float("inf"):
    ans = -1
print(ans)

# Optimized solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, ma, mb = list(map(int, input().split()))
abc = [None]*n
for i in range(n):
    a,b,c = tuple(map(int, input().split()))
    abc[i] = (a*mb - b*ma, c)
abc.sort()
def halfcomb(l):
    n = len(l)
    n1 = n//2
    n2 = (n+1)//2
    l1 = []
    l2 = []
    def sub(v1, v2, i, bound, ll, ind=0):
        if i==bound:
            ll.append((v1,v2))
            return
        sub(v1, v2, i+1, bound, ll, ind)
        sub(v1+l[ind+i][0], v2+l[ind+i][1], i+1, bound, ll, ind)
    sub(0, 0, 0, n1, l1)
    sub(0, 0, 0, n2, l2, ind=n1)
    return l1, l2
l1, l2 = halfcomb(abc)
d2 = {}
for v,c in l2:
    if v in d2:
        d2[v] = min(d2[v], c)
    else:
        d2[v] = c
ans = float("inf")
for v,c in l1:
    if v==0 and c>0:
        ans = min(ans, c)
for v,c in l2:
    if v==0 and c>0:
        ans = min(ans, c)
        
for v,c in l1:
    if -v in d2 and c+d2[-v]>0:
        ans = min(ans, c+d2[-v])
if ans == float("inf"):
    ans = -1
print(ans)
# Original solution
N, Ma, Mb = list(map(int, input().split()))
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = [[inf] * (N_max * b_max + 1) for _ in range(N_max * a_max + 1)]
dp[0][0] = 0

for i, (aa, bb, cc) in enumerate(e):
    for a in reversed(list(range(a_max * i + 1))):
        for b in reversed(list(range(b_max * i + 1))):
            if dp[a][b] == inf: continue
            if a + aa < N_max * a_max + 1 and b + bb < N_max * b_max + 1:
                dp[a + aa][b + bb] = min(dp[a + aa][b + bb], dp[a][b] + cc)

ans = inf
for i in range(1, N_max * a_max + 1):
    if i * Ma >= N_max * a_max + 1 or i * Mb >= N_max * b_max + 1: break
    # a:b=Ma:Mb
    # b*Ma=a*Mb
    ans = min(ans, dp[i * Ma][i * Mb])

print((ans if ans < inf else -1))


# Optimized solution
inf = float('inf')

N, Ma, Mb = list(map(int, input().split()))
dp = [[inf] * (400 + 1) for _ in range(400 + 1)]
dp[0][0] = 0

max_a = 0
max_b = 0
for i in range(N):
    a, b, c = list(map(int, input().split()))
    max_a += a
    max_b += b
    for j in reversed(list(range(max_a + 1 - a))):
        for k in range(max_b + 1 - b):
            if dp[j][k] == inf: continue
            dp[j + a][k + b] = min(dp[j][k] + c, dp[j + a][k + b])

j = Ma
k = Mb
ans = inf
while j < 400 + 1 and k < 400 + 1:
    ans = min(ans, dp[j][k])
    j += Ma
    k += Mb

print((-1 if ans == inf else ans))
# print(dp)
# Original solution
def main():
    inf = 100 * 40 + 1
    mx = 400

    N, Ma, Mb = list(map(int, input().split()))

    dp = [[[inf] * (400 + 1) for _ in range(400 + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        ai, bi, ci = list(map(int, input().split()))
        for a in range(mx + 1):
            for b in range(mx + 1):
                dp[i + 1][a][b] = dp[i][a][b]
        for a in range(ai, mx + 1):
            for b in range(bi, mx + 1):
                dp[i + 1][a][b] = min(
                    dp[i + 1][a][b],
                    dp[i][a - ai][b - bi] + ci
                )
    k = 1
    ans = inf
    while Ma * k <= mx and Mb * k <= mx:
        ans = min(ans, dp[N][Ma * k][Mb * k])
        k += 1

    if ans == inf:
        print((-1))
    else:
        print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    INF = 100 * 40 + 1
    MX = 4000

    N, Ma, Mb = list(map(int, input().split()))

    dp = [[INF] * (MX * 2 + 1) for _ in range(2)]
    i, j = 0, 1
    for _ in range(N):
        ai, bi, ci = list(map(int, input().split()))
        x = Ma * bi - Mb * ai  # Σai:Σbi=Ma:Mb<->Ma*Σbi-Mb*Σai=0

        for k in range(-MX, MX + 1):
            dp[j][k] = dp[i][k]
        dp[j][x] = min(dp[j][x], ci)

        for k in range(-MX + x, MX + 1):
            dp[j][k] = min(
                dp[j][k],
                dp[i][k - x] + ci
            )
        i, j = j, i

    res = dp[i][0]
    print((-1 if res == INF else res))


if __name__ == '__main__':
    main()
# Original solution
def main():
    INF = 100 * 40 + 1
    MX = 4000

    N, Ma, Mb = list(map(int, input().split()))

    dp = [[INF] * (MX * 2 + 1) for _ in range(2)]
    i, j = 0, 1
    for _ in range(N):
        ai, bi, ci = list(map(int, input().split()))
        x = Ma * bi - Mb * ai  # Σai:Σbi=Ma:Mb<->Ma*Σbi-Mb*Σai=0

        for k in range(-MX, MX + 1):
            dp[j][k] = dp[i][k]
        dp[j][x] = min(dp[j][x], ci)

        for k in range(-MX + x, MX + 1):
            dp[j][k] = min(
                dp[j][k],
                dp[i][k - x] + ci
            )
        i, j = j, i

    res = dp[i][0]
    print((-1 if res == INF else res))


if __name__ == '__main__':
    main()


# Optimized solution
# https://atcoder.jp/contests/abc054/submissions/4360181

def main():
    from collections import defaultdict

    INF = 40 * 100 + 1

    N, Ma, Mb = list(map(int, input().split()))

    memo = defaultdict(lambda: INF)

    for _ in range(N):
        ai, bi, ci = list(map(int, input().split()))
        x = Ma * bi - Mb * ai  # Σai:Σbi=Ma:Mb<->Ma*Σbi-Mb*Σai=0

        for key, value in tuple(memo.items()):
            memo[key + x] = min(
                memo[key + x],
                value + ci
            )  # 既存の組み合わせに混合
        memo[x] = min(memo[x], ci)  # 新規のみ

    print((memo[0] if 0 in memo else -1))


if __name__ == '__main__':
    main()
# Original solution
def main():
    n,ma,mb = list(map(int,input().split()))
    dp = [[[float("inf") for _ in range(401)] for _ in range(401)] for _ in range(n+1)]
    dp[0][0][0]=0

    for i in range(1,n+1):
        a,b,c = list(map(int,input().split()))
        for j in range(401):
            for k in range(401):
                if a<=j and b<=k:
                    dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
                else:
                    dp[i][j][k] = dp[i-1][j][k]
    ans = float("inf")
    for i in range(1,401):
        for j in range(1,401):
            if i*mb == j*ma:
                ans = min(ans,dp[n][i][j])
    if ans==float("inf"):
        print((-1))
    else:
        print(ans)
if __name__ == "__main__":
    main()


# Optimized solution
n,ma,mb=list(map(int,input().split()))
dp=[[[10**30 for j in range(401)]for i in range(401)]for k in range(n+1)]
dp[0][0][0]=0 
l=[]
for i in range(n):
    a,b,c=list(map(int,input().split()))
    l.append([a,b,c])
for i in range(1,n+1):
    a,b,c=l[i-1][0],l[i-1][1],l[i-1][2]
    for x in range(401):
        for y in range(401):
            if x<a or y<b:
                dp[i][x][y]=dp[i-1][x][y]
                continue 
            dp[i][x][y]=min(dp[i-1][x][y],dp[i-1][x-a][y-b]+c)
            
mini=10**30 
for i in range(1,40):
    mini=min(mini,dp[n][ma*i][mb*i])
if mini>=10**30 :
    print((-1))
else:
    print(mini)
# Original solution
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce

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

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, Ma, Mb = list(map(int, input().split()))
    dp = [[[INF] * 401 for j in range(401)] for i in range(N + 1)]
    dp[0][0][0] = 0
    a_b_c = [list(map(int, input().split())) for _ in range(N)]

    for i, (a, b, c) in enumerate(a_b_c):
        for j in range(len(dp[0])):
            for k in range(len(dp[0][0])):
                # not use
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])

                # use
                if j + a < len(dp[0]) and k + b < len(dp[0][0]):
                    dp[i + 1][j + a][k + b] = min(dp[i + 1][j + a][k + b], dp[i][j][k] + c)

    ans = INF
    for i in count(1):
        a, b = Ma * i, Mb * i
        if a >= len(dp[0]) or b >= len(dp[0][0]):
            break
        ans = min(ans, dp[-1][a][b])
    if ans != INF:
        print(ans)
    else:
        print((-1))

if __name__ == '__main__':
    main()


# Optimized solution
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce

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

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, Ma, Mb = list(map(int, input().split()))
    dp = [[[INF] * 401 for j in range(401)] for i in range(N + 1)]
    dp[0][0][0] = 0
    a_b_c = [list(map(int, input().split())) for _ in range(N)]

    for i, (a, b, c) in enumerate(a_b_c):
        for j in range(len(dp[0])):
            for k in range(len(dp[0][0])):
                if dp[i][j][k] == INF:
                    continue

                # not use
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])

                # use
                if j + a < len(dp[0]) and k + b < len(dp[0][0]):
                    dp[i + 1][j + a][k + b] = min(dp[i + 1][j + a][k + b], dp[i][j][k] + c)

    ans = INF
    for i in count(1):
        a, b = Ma * i, Mb * i
        if a >= len(dp[0]) or b >= len(dp[0][0]):
            break
        ans = min(ans, dp[-1][a][b])
    if ans != INF:
        print(ans)
    else:
        print((-1))

if __name__ == '__main__':
    main()
# Original solution
from collections import defaultdict

MAX = 40001


def main():
    N, Ma, Mb = [int(a) for a in input().split()]

    abc = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    dp = [
        [
            [MAX for b in range(10 * N + 1)]
            for a in range(10 * N + 1)
        ]
        for i in range(N)
    ]  # dp[i][a][b] = i番目までを使ってaグラムbグラムを作る最小コスト

    a, b, c = abc[0]
    dp[0][a][b] = c
    dp[0][0][0] = 0

    for i in range(1, N):
        a, b, c = abc[i]
        for j in range(10 * N):
            for k in range(10 * N):
                tukawanai = dp[i - 1][j][k]
                if j - a >= 0 and k - b >= 0 and dp[i - 1][j - a][k - b] != MAX:
                    tukau = dp[i - 1][j - a][k - b] + c
                    dp[i][j][k] = min(tukawanai, tukau)
                else:
                    dp[i][j][k] = tukawanai

    res = MAX
    l = dp[-1]
    for a in range(1,10 * N+1):
        aa = a * Mb
        if aa % Ma != 0:
            continue
        b = aa // Ma
        if b >= len(l[a]):
            continue
        c = l[a][b]
        res = min(res, c)

    if res == MAX:
        res = -1
    print(res)


if __name__ == '__main__':
    main()


# Optimized solution
from collections import defaultdict

MAX = 40001


def main():
    N, Ma, Mb = [int(a) for a in input().split()]

    abc = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    dp = [
        [
            [MAX for b in range(10 * N + 1)]
            for a in range(10 * N + 1)
        ]
        for i in range(N)
    ]  # dp[i][a][b] = i番目までを使ってaグラムbグラムを作る最小コスト

    A, B, C = abc[0]
    # dp[0][a][b] = c
    # dp[0][0][0] = 0

    mem = {(0, A, B): C, (0, 0, 0): 0}

    def solve(i, a, b):
        if (i, a, b) in mem:
            return mem[(i, a, b)]
        if i == 0:
            return MAX
        ai, bi, ci = abc[i]
        tukawanai = solve(i - 1, a, b)
        if a - ai >= 0 and b - bi >= 0:
            pre = solve(i - 1, a - ai, b - bi)
            if pre != MAX:
                mem[(i, a, b)] = min(tukawanai, pre + ci)
                return mem[(i, a, b)]
        mem[(i, a, b)] = tukawanai
        return mem[(i, a, b)]

    res = MAX
    for a in range(1, 10 * N + 1):
        aa = a * Mb
        if aa % Ma != 0:
            continue
        b = aa // Ma
        if b >= 10 * N + 1:
            continue
        c = solve(N - 1, a, b)
        res = min(res, c)

    if res == MAX:
        res = -1
    print(res)


if __name__ == '__main__':
    main()
# Original solution
from collections import defaultdict
N,Ma,Mb=list(map(int,input().split()))
A=[]
B=[]
C=[]
a_sum=0
b_sum=0
for i in range(N):
	a,b,c=list(map(int,input().split()))
	A.append(a)
	B.append(b)
	C.append(c)
	a_sum+=a
	b_sum+=b

dp=defaultdict(lambda: float("inf"))
dp[(0,0,0)]=0


for k in range(1,N+1):
	for x in range(a_sum+1):
		for y in range(b_sum+1):
			dp[(k,x,y)]=min( dp[(k,x,y)], dp[(k-1,x,y)] )
			if x-A[k-1]>=0 and y-B[k-1]>=0:
				dp[(k,x,y)]=min( dp[(k-1,x,y)], dp[(k-1, x-A[k-1], y-B[k-1])]+C[k-1] )


ans=float("inf")
for x in range(1,a_sum+1):
	for y in range(1,b_sum+1):
		if x*Mb==y*Ma:
			ans=min(ans,dp[(N, x, y)])

if ans==float("inf"):
	print(-1)
else:
	print(ans)
			

# Optimized solution
from collections import defaultdict
N,Ma,Mb=list(map(int,input().split()))

dp=defaultdict(lambda: float("inf"))
dp[(0,0)]=0

for i in range(N):
	a,b,c=list(map(int,input().split()))
	for j in list(dp.items()):
		x=j[0][0]
		y=j[0][1]
		z=j[1]
		na, nb, nc = x+a, y+b, z+c 
		dp[(na, nb)]=min( dp[(na, nb)], nc)


ans=float("inf")
for i in list(dp.items()):
	x=i[0][0]
	y=i[0][1]
	z=i[1]
	if x==0 and y==0:
		continue
	if x*Mb==y*Ma:
		ans=min(ans,z)

else:
	if ans==float("inf"):
		print(-1)
	else:
		print(ans)
# Original solution
N,Ma,Mb=list(map(int,input().split()))
a=[0 for k in range(N)]
b=[0 for k in range(N)]
c=[0 for k in range(N)]
import copy
for k in range(N):
    a[k],b[k],c[k]=list(map(int,input().split()))
Sa=sum(a)
Sb=sum(b)
dp =[[5000 for k in range(Sb+1)]for k in range(Sa+1)]
dp[0][0]=0
for k in range(N):
    listj=[]
    listl=[]
    co=copy.deepcopy(dp)
    for j in range(Sa-a[k]+1):
        for l in range(Sb-b[k]+1):
            if dp[j][l]!=5000:
                listj.append(j)
                listl.append(l)
    for m in range(len(listl)):
        dp[listj[m]+a[k]][listl[m]+b[k]]=min(co[listj[m]][listl[m]]+c[k], co[listj[m]+a[k]][listl[m]+b[k]])
ans=[5000]
for k in range(1, min(Sa//Ma,Sb//Mb)+1):
    ans.append(dp[Ma*k][Mb*k])
if min(ans)==5000:
    print((-1))
else:
    print((min(ans)))

# Optimized solution
N,Ma,Mb=list(map(int,input().split()))
a=[0 for k in range(N)]
b=[0 for k in range(N)]
c=[0 for k in range(N)]
import copy
for k in range(N):
    a[k],b[k],c[k]=list(map(int,input().split()))
Sa=sum(a)
Sb=sum(b)
dp =[[[5000 for k in range(Sb+1)]for k in range(Sa+1)]for k in range(N+1)]
dp[0][0][0]=0
for k in range(N):
    listj=[]
    listl=[]
    for j in range(Sa-a[k]+1):
        for l in range(Sb-b[k]+1):
            if dp[k][j][l]!=5000:
                listj.append(j)
                listl.append(l)
    for m in range(len(listl)):
        dp[k+1][listj[m]+a[k]][listl[m]+b[k]]=min(dp[k][listj[m]][listl[m]]+c[k], dp[k][listj[m]+a[k]][listl[m]+b[k]])
        dp[k+1][listj[m]][listl[m]]=min(dp[k][listj[m]][listl[m]], dp[k+1][listj[m]][listl[m]])
ans=[5000]
for k in range(1, min(Sa//Ma,Sb//Mb)+1):
    ans.append(dp[-1][Ma*k][Mb*k])
if min(ans)==5000:
    print((-1))
else:
    print((min(ans)))
# Original solution
import math

def f(i):
    if i == ns:
        suma, sumb, sumcost = 0, 0, 0
        for j in range(ns):
            if s[j] == 1:
                suma += x[j][0]
                sumb += x[j][1]
                sumcost += x[j][2]
        mincost[suma][sumb] = min(mincost[suma][sumb], sumcost)
        return
    s[i] = 1
    f(i + 1)
    s[i] = 0
    f(i + 1)

def g(i):
    if i == nt:
        global ans
        suma, sumb, sumcost = 0, 0, 0
        for j in range(nt):
            if t[j] == 1:
                suma += y[j][0]
                sumb += y[j][1]
                sumcost += y[j][2]
        k = 1
        while True:
            ss, tt = k * ma - suma, k * mb - sumb
            if 0 <= ss <= l and 0 <= tt <= l:
                ans = min(ans, mincost[ss][tt] + sumcost)
            elif l < ss or l < tt:
                break
            k += 1
        return
    t[i] = 1
    g(i + 1)
    t[i] = 0
    g(i + 1)

n, ma, mb = list(map(int, input().split()))
ns, nt = int(math.ceil(n / 2)), n // 2
l = 10 * ns
mincost = [[114514] * (l + 5) for _ in range(l + 5)]
ans = 114514
x = [list(map(int, input().split())) for _ in range(ns)]
y = [list(map(int, input().split())) for _ in range(nt)]
s = [0] * ns
t = [0] * nt
f(0)
g(0)
print((ans if not ans == 114514 else -1))

# Optimized solution
n, ma, mb = list(map(int, input().split()))
x = [list(map(int, input().split())) for _ in range(n)]
x.insert(0, [0, 0, 0])
inf = 114514
dp = [[[inf] * (10 * n + 1) for _ in range(10 * n + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0][0] = 0
suma, sumb = 0, 0
for i in range(1, n + 1):
    suma += x[i][0]
    sumb += x[i][1]
    for j in range(suma + 1):
        for k in range(sumb + 1):
            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])
            if j >= x[i][0] and k >= x[i][1]:
                dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - x[i][0]][k - x[i][1]] + x[i][2])
ans = 114514
for i in range(1, 10 * n + 1):
    for j in range(1, 10 * n + 1):
        if i * mb == j * ma:
            ans = min(ans, dp[n][i][j])
print((ans if not ans == 114514 else -1))
# Original solution
N, Ma, Mb = list(map(int, input().split()))
a = [0]*N
b = [0]*N
c = [0]*N
INF = float("inf")


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

#dp[i][j][k]...i番目までの品物で, タイプAの物質をjグラム, タイプBの物質をkグラム調達するのに必要な費用の最小値

dp = [[[INF]*400 for _ in range(400)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    for j in range(400):
        for k in range(400):
            if j < a[i-1] or k < b[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i-1]][k-b[i-1]]+c[i-1])

ans = INF

for i in range(1, N+1):
    for j in range(1, 400):
        for k in range(1, 400):
            if j*Mb == k*Ma:
                ans = min(ans, dp[i][j][k])
if ans == INF:
    print((-1))
else:
    print(ans)




# Optimized solution
N, Ma, Mb = list(map(int, input().split()))
a = [0]*N
b = [0]*N
c = [0]*N
INF = 10000


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

#dp[i][j][k]...i番目までの品物で, タイプAの物質をjグラム, タイプBの物質をkグラム調達するのに必要な費用の最小値

dp = [[[INF]*400 for _ in range(400)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    for j in range(400):
        for k in range(400):
            if j < a[i-1] or k < b[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i-1]][k-b[i-1]]+c[i-1])

ans = INF

for i in range(1, N+1):
    for j in range(1, 400):
        for k in range(1, 400):
            if j*Mb == k*Ma:
                ans = min(ans, dp[i][j][k])
if ans == INF:
    print((-1))
else:
    print(ans)
# Original solution
def main():
	n, ma, mb, *L = list(map(int, open(0).read().split()))
	M = 1<<30
	dp = [[M] * 420 for _ in range(420)]
	dp[0][0] = 0
	for a, b, c in zip(*[iter(L)] * 3):
		for i in range(400, -1, -1):
			for j in range(400, -1, -1):
				t = dp[i][j] + c
				if dp[i + a][j + b] > t:
					dp[i + a][j + b] = t
	ans = M
	_ma, _mb = ma, mb
	while _ma < 410 > _mb:
		ans = min(ans, dp[_ma][_mb])
		_ma += ma
		_mb += mb
	print((ans if ans < M else -1))

if __name__=="__main__":
	main()

# Optimized solution
def main():
	n, ma, mb, *L = list(map(int, open(0).read().split()))
	M = 1 << 30
	dp = [[M] * 420 for _ in range(420)]
	dp[0][0] = 0
	ua = ub = 15
	for a, b, c in zip(*[iter(L)] * 3):
		for i in range(ua, -1, -1):
			for j in range(ub, -1, -1):
				t = dp[i][j] + c
				if dp[i + a][j + b] > t:
					dp[i + a][j + b] = t
					if ua < i + a:
						ua = i + a
					if ub < j + b:
						ub = j + b
	ans = M
	_ma, _mb = ma, mb
	while _ma < 410 > _mb:
		ans = min(ans, dp[_ma][_mb])
		_ma += ma
		_mb += mb
	print((ans if ans < M else -1))


if __name__ == "__main__":
	main()