Dolphin is planning to generate a small amount of a certain chemical substance C.

In order to generate the substance C, he must prepare a solution which is a mixture of two substances A and B in the ratio of M_a:M_b.

He does not have any stock of chemicals, however, so he will purchase some chemicals at a local pharmacy.

The pharmacy sells N kinds of chemicals. For each kind of chemical, there is exactly one package of that chemical in stock.

The package of chemical i contains a_i grams of the substance A and b_i grams of the substance B, and is sold for c_i yen (the currency of Japan).

Dolphin will purchase some of these packages. For some reason, he must use all contents of the purchased packages to generate the substance C.

Find the minimum amount of money required to generate the substance C.

If it is not possible to generate the substance C by purchasing any combination of packages at the pharmacy, report that fact.  

-----Constraints-----
 - 1≦N≦40 
 - 1≦a_i,b_i≦10 
 - 1≦c_i≦100 
 - 1≦M_a,M_b≦10 
 - gcd(M_a,M_b)=1
 - a_i, b_i, c_i, M_a and M_b are integers.

-----Input-----
The input is given from Standard Input in the following format:
N M_a M_b  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_N b_N c_N  

-----Output-----
Print the minimum amount of money required to generate the substance C. If it is not possible to generate the substance C, print -1 instead.

-----Sample Input-----
3 1 1
1 2 1
2 1 2
3 3 10

-----Sample Output-----
3

The amount of money spent will be minimized by purchasing the packages of chemicals 1 and 2.

In this case, the mixture of the purchased chemicals will contain 3 grams of the substance A and 3 grams of the substance B, which are in the desired ratio: 3:3=1:1.

The total price of these packages is 3 yen.

Difficulty: interview

Starter code:

Solutions:
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))


def __starting_point():
	main()

__starting_point()

N, ma, mb = list(map(int, input().split()))
a = [0]*N
b = [0]*N
c = [0]*N
NMAX = 40
ABMAX = 10
INF = 1000000
for i in range(N):
    a[i], b[i], c[i] = list(map(int, input().split()))
dp = [[[INF]*(NMAX*ABMAX+1)for _ in range(NMAX*ABMAX+1)]for _ in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for ca in range(NMAX*ABMAX+1):
        for cb in range(NMAX*ABMAX+1):
            if dp[i][ca][cb] == INF:
                continue
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            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 = INF
for ca in range(1, NMAX*ABMAX+1):
    for cb in range(1, NMAX*ABMAX+1):
        if ca * mb == cb * ma:
            ans = min(ans, dp[N][ca][cb])
print((ans if ans != INF else -1))


#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools
#from scipy.misc import comb

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

DP = [[10**9 for _ in range(401)] for _ in range(401)]
DP[0][0] = 0
for _ in range(N):
    a,b,c = map(int, input().split())
    for i in range(401)[::-1]:
        for j in range(401)[::-1]:
            if DP[i][j] != 10**9:
                DP[i+a][j+b] = min(DP[i+a][j+b], DP[i][j]+c)

ans = 10**9
A,B = Ma, Mb
while max(A,B) <= 400:
    ans = min(ans, DP[A][B])
    A += Ma
    B += Mb

if ans == 10**9:
    print(-1)
else:
    print(ans)

N,Ma,Mb=map(int,input().split())
INF=40*100+1
dp=[[INF for i in range(10*N+1)] for j in range(10*N+1)]
dp[0][0]=0
ans=INF
for p in range(N):
  a,b,c=map(int,input().split())
  for i in range(len(dp)-1,-1,-1):
    for j in range(len(dp[i])-1,-1,-1):
      if dp[i][j]!=INF:
        dp[i+a][j+b]=min(dp[i+a][j+b],dp[i][j]+c)
        if (i+a)/(j+b)==Ma/Mb:
          ans=min(ans,dp[i+a][j+b])
          
if ans==INF:
  print(-1)
else:
  print(ans)


N, Ma, Mb = list(map(int,input().split()))
rate = Ma / Mb
a = [0] * N
b = [0] * N
c = [0] * N
MA = 0
MB = 0
MC = 0
for i in range(N):
    a[i], b[i], c[i] = list(map(int, input().split()))
    MA += a[i]
    MB += b[i]
    MC += c[i]
    
dp = [[[MC for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0] = 0

for it_N in range(N):
    for it_MA in range(MA+1):
        for it_MB in range(MB+1):
            if it_MA >= a[it_N] and it_MB >= b[it_N]:
                if dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] != MC:
                    dp[it_N+1][it_MA][it_MB] = min(dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] + c[it_N], dp[it_N][it_MA][it_MB])
                else:
                    dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]
            else:
                dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]

ans = -1
for a in range(1, MA+1):
    for b in range(1, MB+1):
        if a/b == rate and dp[N][a][b] != MC:
            if ans == -1:
                ans = dp[N][a][b]
            else:
                ans = min(dp[N][a][b], ans)
print(ans)


n,MA,MB=map(int,input().split())
INF=10**10
A=[]
B=[]
C=[]
for i in range(n):
  a,b,c=map(int,input().split())
  if MA*b-MB*a>0:
    A.append([MA*b-MB*a,c])
  elif MA*b-MB*a<0:
    B.append([MB*a-MA*b,c])
  else:
    C.append(c)
dp1=[[INF]*10010 for i in range(len(A)+1)]
for i in range(1,len(A)+1):
  for j in range(1,10010):
    if j<A[i-1][0]:
      dp1[i][j]=dp1[i-1][j]
    elif j==A[i-1][0]:
      dp1[i][j]=min(A[i-1][1],dp1[i-1][j])
    else:
      dp1[i][j]=min(dp1[i-1][j],dp1[i-1][j-A[i-1][0]]+A[i-1][1])
dp2=[[INF]*10010 for i in range(len(B)+1)]
for i in range(1,len(B)+1):
  for j in range(1,10010):
    if j<B[i-1][0]:
      dp2[i][j]=dp2[i-1][j]
    elif j==B[i-1][0]:
      dp2[i][j]=min(B[i-1][1],dp2[i-1][j])
    else:
      dp2[i][j]=min(dp2[i-1][j],dp2[i-1][j-B[i-1][0]]+B[i-1][1])
ans=INF
for i in range(10010):
  a=dp1[-1][i]+dp2[-1][i]
  if a<ans:
    ans=a
for i in range(len(C)):
  if C[i]<ans:
    ans=C[i]
if ans<INF:
  print(ans)
else:
  print(-1)

n,ma,mb=list(map(int,input().split()))
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)
sa1=sa+1
sb1=sb+1

inf=1000000
x=[[inf]*(sb1) for i in range(sa1)]
x[0][0]=0
for i in range(n):
    now=el[i]
    x_sub=[[0]*(sb1) for i in range(sa1)]
    for k in range(sa1):
        for l in range(sb1):
            if x[k][l]!=inf:
                if k+now[0]<sa1:
                    if l+now[1]<sb1:
                        x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    for k in range(sa1):
        for l in range(sb1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print((-1))
else:
    print(ans)


n,ma,mb=list(map(int,input().split()))
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)
sa1=sa+1
sb1=sb+1

inf=10000000000
x=[[inf]*(sb1) for i in range(sa1)]
x[0][0]=0
for i in range(n):
    now=el[i]
    x_sub=[[0]*(sb1) for i in range(sa1)]
    for k in range(sa1):
        for l in range(sb1):
            if x[k][l]!=inf and k+now[0]<sa1 and l+now[1]<sb1:
                x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    for k in range(sa1):
        for l in range(sb1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print((-1))
else:
    print(ans)


import sys
from itertools import combinations
input = sys.stdin.readline

def main():
    n, ma, mb = list(map(int, input().split()))
    dp = [[0]*401 for _ in range(401)]
    
    for _ in range(n):
        a, b, c = list(map(int, input().split()))
        for i in range(400, -1, -1):
            for j in range(400, -1, -1):
                if i == 0 and j == 0:
                    if dp[a][b]:
                        dp[a][b] = min(dp[a][b], c)
                    else:
                        dp[a][b] = c
                if dp[i][j] and i+a <= 400 and j+b <= 400:
                    if dp[i+a][j+b]:
                        dp[i+a][j+b] = min(dp[i+a][j+b], dp[i][j]+c)
                    else:
                        dp[i+a][j+b] = dp[i][j] + c
    
    ans = 1000000
    x, y = ma, mb
    while x <= 400 and y <= 400:
        if dp[x][y]:
            ans = min(dp[x][y], ans)
        x += ma
        y += mb
    if ans == 1000000:
        print((-1))
    else:
        print(ans)
    
def __starting_point():
    main()

__starting_point()

N, A, B = map(int, input().split())
X = [1<<20] * 4040
for _ in range(N):
    a, b, c = map(int, input().split())
    t = A*b-B*a
    X = [min(X[i], (0 if (i-t)%4040 == 0 else X[(i-t)%4040]) + c) for i in range(4040)]
print(-1 if X[0] > 1<<18 else X[0])

INF = float('inf')
n, ma, mb = list(map(int, input().split()))
cmax = n * 10
t = [[INF] * (cmax + 1) for _ in range(cmax + 1)]
for _ in range(n):
  a, b, c = list(map(int, input().split()))
  for aa in range(cmax, 0, -1):
    for bb in range(cmax, 0, -1):
      if t[aa][bb] == INF:
        continue
      t[aa + a][bb + b] = min(t[aa + a][bb + b], t[aa][bb] + c)
  t[a][b] = min(t[a][b], c)
result = INF
for a in range(1, cmax):
  for b in range(1, cmax):
    if a * mb == b * ma:
      result = min(result, t[a][b])
if result == INF:
  result = -1
print(result)


N, Ma, Mb = list(map(int, input().split()))
items = [[int(x) for x in input().split()] for _ in range(N)]

A, B = 0, 0
for a, b, _ in items:
    A += a
    B += b

dp = [[[float("inf")] * (B + 1) for _ in range(A + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0][0] = 0

for i in range(N):
    a, b, c = items[i]
    for j in range(A + 1):
        for k in range(B + 1):
            if j - a >= 0 and k - b >= 0:
                dp[i + 1][j][k] = min(dp[i][j - a][k - b] + c, dp[i][j][k])
            else:
                dp[i + 1][j][k] = dp[i][j][k]


ans = float("inf")
for x in range(1, min(A // Ma, B // Mb) + 1):
    a = Ma * x
    b = Mb * x
    ans = min(dp[N][a][b], ans)

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


N, A, B = map(int, input().split())
X = [1<<20] * 8080
for _ in range(N):
    a, b, c = map(int, input().split())
    t = A*b-B*a
    X = [min(X[i], (0 if (i-t)%8080 == 0 else X[(i-t)%8080]) + c) for i in range(8080)]
print(-1 if X[0] > 1<<18 else X[0])

N,MA,MB = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(N)]

INF = float('inf')
from collections import defaultdict
dp = defaultdict(lambda: INF)
dp[(0,0)] = 0
for a,b,c in ABC:
    dp2 = defaultdict(lambda: INF)
    for (pa,pb),pc in dp.items():
        dp2[(pa,pb)] = min(dp2[(pa,pb)], pc)
        dp2[(pa+a, pb+b)] = min(dp2[(pa+a, pb+b)], pc+c)
    dp = dp2

ans = INF
for i in range(1,401):
    ans = min(ans, dp[(MA*i, MB*i)])
print(-1 if ans==INF else ans)

# DP
INF = float('inf')

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

cmax = N * 10
t = [[INF] * (cmax + 1) for _ in range(cmax + 1)]
for _ in range(N):
    a, b, c = list(map(int, input().split()))
    for aa in range(cmax, 0, -1):
        for bb in range(cmax, 0, -1):
            if t[aa][bb] == INF:
                continue
            t[aa + a][bb + b] = min(t[aa + a][bb + b], t[aa][bb] + c)
    t[a][b] = min(t[a][b], c)

result = INF
for a in range(1, cmax):
    for b in range(1, cmax):
        if a * Mb == b * Ma:
            result = min(result, t[a][b])
if result == INF:
    result = -1
print(result)


# coding: utf-8
# Your code here!
N,Ma,Mb=list(map(int,input().split()))

dp=[[10**9 for i in range(401)] for j in range(401)]
dp[0][0]=0

for _ in range(N):
    a,b,c=list(map(int,input().split()))
    for i in range(401)[::-1]:
        for j in range(401)[::-1]:
            if dp[i][j]!=10**9:
                dp[i+a][j+b]=min(dp[i+a][j+b],dp[i][j]+c)

ans=10**9
for i in range(Ma,401)[::Ma]:
    j=i//Ma*Mb
    if j>=401:
        break
    ans=min(ans,dp[i][j])

if ans==10**9:
    print((-1))
else:
    print(ans)
    


import numpy as np
N, Ma, Mb = map(int, input().split())
ls = []
dp = np.full((1001,1001),float('inf'))
dp[0][0] = 0
for i in range(N):
  a,b,c = map(int, input().split())
  dp[a:,b:] = np.minimum(dp[:1001-a,:1001-b]+c, dp[a:,b:])
ans = float('inf')
for i in range(1,1001):
  if i*Ma>1000 or i*Mb>1000:
    break
  if dp[i*Ma,i*Mb]<ans:
    ans = dp[i*Ma,i*Mb]
if ans==float('inf'):
  ans = -1
print(int(ans))

# 半分全列挙バージョン
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def allptn(abc,ma,mb):
    inf=10**9
    # a,b,cの全組合せを作る
    allabc=[(0,0,0)]
    for a,b,c in abc:
        n=len(allabc)
        for i in range(n):
            aa,bb,cc=allabc[i]
            allabc.append((aa+a,bb+b,cc+c))
    # 指標とコストの組合せにする
    # 指標が重複するときはコストが小さいほうだけ残す
    # 指標が0のときは前後半で組み合わせる必要がないので単独で答えを出しておく
    vc={}
    ans=inf
    for a,b,c in allabc[1:]:
        val=a*mb-b*ma
        if val:
            pc=vc.setdefault(val,inf)
            if c<pc:vc[val]=c
        else:
            if c<ans:ans=c
    res=[(val,c) for val,c in sorted(vc.items())]
    return ans,res

def main():
    n,ma,mb=MI()
    abc=[LI() for _ in range(n)]
    inf=10**9
    # 前半の要素をa1,b1、後半の要素をa2,b2とする
    # (a1+a2):(b1+b2)=ma:mbとなればよい。式変形すると
    # (mb*a1-ma*b1)+(mb*a2-ma*b2)=0となる
    # つまり各要素についてmb*a-ma*bという指標を計算し、前半と後半で和が0になる組合せを探せばよい
    # 前半全列挙
    ans,pre=allptn(abc[:n//2],ma,mb)
    # 後半全列挙
    ret,pos=allptn(abc[n//2:],ma,mb)
    ans=min(ans,ret)
    # 指標が昇順になるよう並び替えて、前半は前から後半は後からしゃくとり法で
    # 指標の和が0になるところのコストを求める
    j=len(pos)-1
    for val,c in pre:
        while val+pos[j][0]>0 and j:j-=1
        if val+pos[j][0]==0:ans=min(ans,c+pos[j][1])
    if ans==inf:print(-1)
    else:print(ans)

main()

nmax, abmax, inf = 40, 10, 1000000

dp = [[[inf] * (nmax * abmax + 1) for _ in range(nmax * abmax + 1)] for _ in range(nmax + 1)]

n, ma, mb = list(map(int, input().split()))

dp[0][0][0] = 0

for i in range(n):
  a, b, c = list(map(int, input().split()))
  dpi = dp[i]
  dpi1 = dp[i + 1]
  for ca in range(0, 401):
    for cb in range(0, 401):
      if dpi[ca][cb] == inf:
        continue
      dpi1[ca][cb] = min(dpi1[ca][cb], dpi[ca][cb])
      dpi1[ca + a][cb + b] = min(dpi1[ca + a][cb + b], dpi[ca][cb] + c)

ans = inf
dpn = dp[n]
for ca in range(1, 401):
  for cb in range(1, 401):
    if ca * mb == cb * ma:
      ans = min(ans, dpn[ca][cb])

if ans == inf:
  ans = -1

print(ans)


import numpy as np

n, ma, mb = map(int, input().split())
U = 400
dp = np.full((U+1, U+1), float("inf"))
dp[0, 0] = 0
for i in range(n):
  a, b, c = map(int, input().split())
  np.minimum(dp[a:, b:], dp[:-a, :-b]+c, out=dp[a:, b:])
ans = float("inf")
for i in range(1, 1+U//max(ma, mb)):
  na, nb = i*ma, i*mb
  ans = min(ans, dp[na, nb])
if ans == float("inf"):
  print(-1)
else:
  print(int(ans))

n,ma,mb= map(int,input().split())
al=[]
bl=[]
cl=[]
for _ in range(n):
    a,b,c= map(int,input().split())
    al.append(a)
    bl.append(b)
    cl.append(c)
suma=sum(al)
MAX=999999999999
gmincost = [MAX]
def dfsMa(id,count,sel):
    if id==n:return
    dfsMa(id+1,count,sel)
    tempsum = al[id]+count
    bsum=costsum=0
    for j in sel+[id]:
        bsum+=bl[j]
        costsum+=cl[j]
    if costsum > gmincost[0]:
        return
    elif tempsum%ma == 0:
        k=tempsum//ma
        if bsum==k*mb:
            gmincost[0] = min(gmincost[0],costsum)
            return
    dfsMa(id+1,count+al[id],sel+[id])
    return
dfsMa(0,0,[])
if gmincost[0]==MAX:print(-1)
else:print(gmincost[0])

n,ma,mb = list(map(int,input().split()))
l = []
sum_a = 0
sum_b = 0
for _ in range(n):
    a,b,c = list(map(int,input().split()))
    sum_a += a
    sum_b += b
    l.append([a,b,c])

INF = 10**10
dp = list( list([INF for i in range(450)] for i in range(450)) for i in range(45))
dp[0][0][0] = 0
for i in range(n):
    for s in range(sum_a+1):
        for k in range(sum_b+1):
            a,b,c = l[i]
            dp[i+1][s][k] = min(dp[i][s][k], dp[i+1][s][k],dp[i][s-a][k-b]+c)

ans = 10**10
k = 1
while ma*k < 450 and mb*k < 450 :
    ans = min(ans, dp[n][ma*k][mb*k])
    k += 1
if ans != 10**10:
  print(ans)
else:
  print((-1))


import copy

N, Ma, Mb = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for _ in range(N)]

INF, W = 10 ** 10, 10 * 10 * N
dp = [[INF] * (2 * W + 1)]

for a, b, c in ABC:
    dp.append(copy.deepcopy(dp[-1]))
    df = a * Mb - b * Ma
    dp[-1][df] = min(c, dp[-1][df])
    for d in range(-W, W + 1):
        dp[-1][df + d] = min(c + dp[-2][d], dp[-1][df + d])

print(("-1" if dp[N][0] == INF else dp[N][0]))


inf = 10 ** 18

a = []
b = []
c = []
n, ma, mb = list(map(int, input().split()))

for _ in range(n):
    a_, b_, c_ = list(map(int, input().split()))
    a.append(a_)
    b.append(b_)
    c.append(c_)

abmax = 10
p = n * abmax
dp = [[[inf for _ in range(p + 1)] for _ in range(p + 1)]
      for _ in range(n + 1)]
dp[0][0][0] = 0

for i in range(n):
    for j in range(p + 1):
        for k in range(p + 1):
            if dp[i][j][k] == inf:
                continue
            dp[i + 1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            dp[i + 1][j + a[i]][k + b[i]
                                ] = min(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k] + c[i])

ans = inf
for j in range(p)[1::]:
    for k in range(p)[1::]:
        if j * mb == k * ma:
            ans = min(ans, dp[n][j][k])

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


n, ma, mb = map(int, input().split())
abc = []
for _ in range(n):
    a, b, c = map(int, input().split())
    abc.append((a, b, c))
dp = {(0, 0): 0}
for a, b, c in abc:
    newdp = dp.copy()
    for (ka, kb), p in dp.items():
        k = (a+ka, b+kb)
        if k in newdp:
            newdp[k] = min(newdp[k], p+c)
        else:
            newdp[k] = p+c
    dp = newdp
INF = 10**10
ans = INF
for (a, b), c in dp.items():
    if ma*b!=mb*a or a==b==0:
        continue
    ans = min(ans, c)
if ans==INF:
    print(-1)
else:
    print(ans)

NMAX=40
ABMAX=10
INF=1000000
N,MA,MB=list(map(int,input().split()))
A=[0]*NMAX
B=[0]*NMAX
C=[0]*NMAX
dp=[[[INF for _ in range(NMAX*ABMAX+1)] for _ in range(NMAX*ABMAX+1)] for _ in range(NMAX+1)]
for i in range(N):
  A[i],B[i],C[i]=list(map(int,input().split()))

dp[0][0][0]=0
for i in range(N):
  for ca in range(NMAX*ABMAX+1):
    for cb in range(NMAX*ABMAX+1):
      if dp[i][ca][cb]==INF: continue
      dp[i+1][ca][cb]=min(dp[i+1][ca][cb],dp[i][ca][cb])
      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=INF
for ca in range(1,NMAX*ABMAX+1):
  for cb in range(1,NMAX*ABMAX+1):
    if ca*MB==cb*MA: ans=min(ans,dp[N][ca][cb])
if ans==INF: ans=-1
print(ans)


N, Ma, Mb = list(map(int, input().split()))
dp = [{} for i in range(N+1)]
dp[0][(0, 0)] = 0
for i in range(N):
  a, b, c = list(map(int, input().split()))
  for p, q in dp[i]:
    if (p, q) not in dp[i+1]: dp[i+1][(p, q)] = 100000
    dp[i+1][(p, q)] = min(dp[i+1][(p, q)], dp[i][(p, q)])
    if (p+a, q+b) not in dp[i+1]: dp[i+1][(p+a, q+b)] = 100000
    dp[i+1][(p+a, q+b)] = min(dp[i+1][(p+a, q+b)], dp[i][(p, q)]+c)
#print(dp[N])
rs = []
for k in range(1, 10000):
  if (k*Ma, k*Mb) in dp[N]:
    r = dp[N][(k*Ma, k*Mb)]
    rs.append(r)
if len(rs) == 0:
  print((-1))
else:
  r = min(rs)
  print(r)


def main():
    N, Ma, Mb = list(map(int, input().split()))
    A = []
    B = []
    C = []
    for _ in range(N):
        a, b, c = list(map( int, input().split()))
        A.append(a)
        B.append(b)
        C.append(c)
    dp = [[10**5]*401 for _ in range(401)]
    dp[0][0] = 0
    for t in range(N):
        a, b, c = A[t], B[t], C[t]
        for i in range(400,-1,-1):
            for j in range(400,-1,-1):
                if i-a >= 0 and j-b >= 0:
                    if dp[i-a][j-b] + c < dp[i][j]:
                        dp[i][j] = dp[i-a][j-b] + c
    ans = 10**5
    for i in range(1, 401):
        if i*Ma > 400 or i*Mb > 400:
            break
        if dp[i*Ma][i*Mb] < ans:
            ans = dp[i*Ma][i*Mb]
    if ans == 10**5:
        print((-1))
    else:
        print(ans)
    
def __starting_point():
    main()

__starting_point()

n, ma, mb = [int(i) for i in input().split()]
lst = [[int(i) for i in input().split()] for _ in range(n)]
lst.sort(key=lambda x: x[2])
dic = {}
def push(k,v):
    if k in dic:
        dic[k] = min(dic[k],v)
    else:
        dic[k] = v


for i in lst:
    k, v = i[0] * mb - i[1] * ma, i[2]
    l = [[j, dic[j]] for j in dic]
    for item in l:
        push(item[0] + k, item[1] + v)
    push(k, v)

print(dic[0] if 0 in dic else '-1')

n, ma, mb = map(int, input().split(" "))
info_med = []
for _ in range(n):
  info_med.append(list(map(int, input().split(" "))))
info_med.sort(key=lambda x: x[2])
dp = []
dp.append([(0, 0, [-1])])

for min_c in range(1, n * 100 + 1):
  temp_list = []
  for i, (a, b, c) in enumerate(info_med):
    if min_c - c >= 0:
      for pre_a, pre_b, pre_i in dp[min_c - c]:
        if pre_i[-1] < i:
          if (a + pre_a) * mb == (b + pre_b) * ma:
            print(min_c)
            return
          temp_list.append((a + pre_a, b + pre_b, pre_i + [i]))
  dp.append(temp_list)
print("-1")

n, A, B = map(int, input().split())
z = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 18

d = {(0, 0):0}
for a, b, cost in z:
    newd = []
    for (x, y), c in d.items():
        new = (a+x, b+y)
        if new not in d or d[new] > c + cost:
            newd.append((new, c+cost))
    for new, newc in newd:
        d[new] = newc

ans = inf
for i in range(1, 10 * n):
    t = (A * i, B * i)
    if t in d:
        ans = min(ans, d[t])
if ans == inf:
    print(-1)
else:
    print(ans)

def half_enumeration(a, *, func):
    """正しい英訳は不明"""
    n = len(a)
    h = n // 2

    def enum(h, *, second_half: bool = False) -> set:
        p = set()
        if second_half:
            b = a[h:]
        else:
            b = a[:h]

        for x in b:
            q = set()
            for e in p:
                q.add(func(e, x))
            p.add(x)
            p.update(q)
        return p

    return enum(h), enum(h, second_half=True)


def main():
    INF = 40 * 100 + 1

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

    def update(e, x):
        return e[0] + x[0], e[1] + x[1]

    xcs = []
    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
        xcs.append((x, ci))

    p1, p2 = half_enumeration(xcs, func=update)

    t1 = [INF] * (INF * 2 + 1)
    t2 = [INF] * (INF * 2 + 1)
    for x, c in p1:
        t1[x] = min(t1[x], c)
    for x, c in p2:
        t2[x] = min(t2[x], c)

    ans = min(t1[0], t2[0])
    for x in range(-INF, INF + 1):
        ans = min(ans, t1[x] + t2[-x])

    print((-1 if ans == INF else ans))


def __starting_point():
    main()

__starting_point()

INF = float('inf')
MAXAB = 10
n, ma, mb = list(map(int, input().split()))
t = [[INF] * (n * MAXAB + 1) for _ in range(n * MAXAB + 1)]
t[0][0] = 0
for _ in range(n):
  a, b, c = list(map(int, input().split()))
  for aa in range(n * MAXAB, -1, -1):
    for bb in range(n * MAXAB, -1, -1):
      if t[aa][bb] == INF:
        continue
      if t[a + aa][b + bb] > t[aa][bb] + c:
        t[a + aa][b + bb] = t[aa][bb] + c
result = INF
for a in range(1, n * MAXAB + 1):
  for b in range(1, n * MAXAB + 1):
    if a * mb == b * ma and result > t[a][b]:
      result = t[a][b]
if result == INF:
  result = -1
print(result)


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))


def __starting_point():
    main()

__starting_point()

import sys

INF = float('inf')

n, ma, mb = map(int, sys.stdin.readline().split())
a, b, c = [], [], []
for _ in range(n):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    a.append(ai); b.append(bi); c.append(ci)

def main():
    sa = sum(a)
    sb = sum(b)
    res = [[[INF] * (sb + 1) for _ in range(sa + 1)] for _ in range(n + 1)]
    res[0][0][0] = 0
    for i in range(n):
        for j in range(sa + 1):
            for k in range(sb + 1):
                if j >= a[i] and k >= b[i]:
                    res[i+1][j][k] = min(res[i][j-a[i]][k-b[i]] + c[i], res[i][j][k])
                else:
                    res[i+1][j][k] = res[i][j][k]
    ans = INF
    for i in range(1, min(sa//ma, sb//mb)+1):
        ans = min(ans, res[n][ma * i][mb * i])
    
    if ans == INF:
        return -1
    else:
        return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

# A,Bそれぞれの最大値は40 * 10である
# dp[i][j] = Aがiグラム、Bがjグラム含まれた薬品の最小コスト

import sys
readline = sys.stdin.readline

N,Ma,Mb = map(int,readline().split())
INF = 10 ** 10
dp = [[INF] * (401) for i in range(401)]
dp[0][0] = 0

for _ in range(N):
  a,b,c = map(int,readline().split())
  for i in range(len(dp) - 1, -1, -1):
    for j in range(len(dp[i]) - 1, -1, -1):
      if dp[i][j] == INF:
        continue
      if dp[i + a][j + b] > dp[i][j] + c:
        dp[i + a][j + b] = dp[i][j] + c

ans = INF
import math
for i in range(1, len(dp)):
  for j in range(1, len(dp)):
    g = math.gcd(i,j)
    if i // g == Ma and j // g == Mb:
      if ans > dp[i][j]:
        ans = dp[i][j]
      
if ans == INF:
  print(-1)
else:
  print(ans)

#masoyさんのコード

import numpy as np

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

dp = np.zeros((U + 1, U + 1), dtype = np.int64)
temp = np.zeros_like(dp)

INF = 10 ** 18
dp += INF
dp[0, 0] = 0

for _ in range(N):
    a, b, c = list(map(int, input().split()))
    temp[:] = dp.copy()
    temp[a:, b:] = np.minimum(temp[a:, b:], dp[:-a, :-b] + c)
    dp = temp #毎回、一つ前の結果を残す

answer = INF
for t in range(1, 401):
    a = Ma * t
    b = Mb * t
    if max(a, b) >= U: #到達できない量に達したら終了
        break
    answer = min(answer, dp[a, b])

if answer == INF:
    answer = -1

print (answer)


N, Ma, Mb = map(int, input().split(' '))
med = []
for _ in range(N):
    med.append(tuple(map(int, input().split(' '))))
inf = 10 ** 9 + 7

dp = [[inf for _ in range(401)] for _ in range(401)]
dp[0][0] = 0

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

ans = inf
for i in range(401):
    for j in range(401):
        if i == 0 or j == 0:
            continue
        if i * Mb == j * Ma:
            ans = min(ans, dp[i][j])
print(ans if ans != inf else -1)

def main():

    N, Ma, Mb = map(int, input().split())
    drug = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        drug.append([a, b, c])

    cur = dict()
    cur[(0, 0)] = 0
    for i in range(N):
        temp = cur.copy()
        for p in cur:
            a, b = p[0]+drug[i][0], p[1]+drug[i][1]

            if (a, b) not in temp:
                temp[(a, b)] = cur[p] + drug[i][2]
            else:
                temp[(a, b)] = min(temp[(a, b)], cur[p]+drug[i][2])
        cur = temp

    # print(cur)
    min_c = float('inf')
    for p in cur:
        if p != (0, 0) and p[0]*Mb == p[1]*Ma:
            min_c = min(min_c, cur[p])
    if min_c == float('inf'):
        return -1
    else:
        return min_c

def __starting_point():
    print(main())
__starting_point()

import copy

N, Ma, Mb = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for _ in range(N)]

INF, W = 10 ** 10, N * 10 * max(Ma, Mb)
dp = [[INF] * (W * 2 + 1)]

for a, b, c in ABC:
    dp.append(copy.deepcopy(dp[-1]))
    df = a * Mb - b * Ma
    dp[-1][df + W] = min(dp[-1][df + W], c)
    for d in range(-W, W + 1):
        if not dp[-2][d] == INF:
            dp[-1][df + d] = min(c + dp[-2][d], dp[-2][df + d], dp[-1][df + d])

print(("-1" if dp[N][W] == INF else dp[N][W]))


n,ma,mb=list(map(int,input().split()))
abc=[list(map(int,input().split())) for _ in range(n)]
import numpy as np
dp=np.full((401,401),4001,int)
dp[0,0]=0
for a,b,c in abc:
  dp[a:,b:]=np.minimum(dp[a:,b:],dp[:-a,:-b]+c)
ma_,mb_=ma,mb
ans=4001
while max(ma_,mb_)<401:
  ans=min(ans,dp[ma_,mb_])
  ma_+=ma
  mb_+=mb
print((ans if ans<4001 else -1))


n,ma,mb=list(map(int,input().split()))
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)
#mi=min(sa//ma,sb//mb)
inf=10000000000
x=[[inf for j in range(sb+1)] for i in range(sa+1)]
x[0][0]=0
for i in range(n):
    now=el[i]
    x_sub=[[0 for j in range(sb+1)] for i in range(sa+1)]
    for k in range(sa+1):
        for l in range(sb+1):
            if x[k][l]!=inf and k+now[0]<sa+1 and l+now[1]<sb+1:
                x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    for k in range(sa+1):
        for l in range(sb+1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print((-1))
else:
    print(ans)


n, ma, mb = [int(i) for i in input().split()]

# a,b,cを入力
lst = [[int(i) for i in input().split()] for _ in range(n)]

# コストの小さい順に並び替える
lst.sort(key=lambda x: x[2])
#print(lst)

dic = {}
#####
# 動的計画法

# 値の更新
def push(k,v):
    if k in dic:
        dic[k] = min(dic[k],v)
    else:
        dic[k] = v

for i in lst:
    # v = i[2]: コスト
    k, v = i[0] * mb - i[1] * ma, i[2]
    l = [[j, dic[j]] for j in dic]
    #print(l)
    for item in l:
        push(item[0] + k, item[1] + v)
    push(k, v)

#####
print((dic[0] if 0 in dic else '-1'))


def main():
    n, ma, mb = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [{} for _ in range(n+1)]
    dp[0][(0, 0)] = 0
    for i in range(n):
        for ky in dp[i].keys():
            if ky in dp[i+1]:
                if dp[i+1][ky] > dp[i][ky]:
                    dp[i+1][ky] = dp[i][ky]
            else:
                dp[i+1][ky] = dp[i][ky]
            t = (ky[0]+arr[i][0], ky[1]+arr[i][1])
            if t in dp[i+1]:
                if dp[i+1][t] > dp[i][ky]+arr[i][2]:
                    dp[i+1][t] = dp[i][ky]+arr[i][2]
            else:
                dp[i+1][t] = dp[i][ky]+arr[i][2]
    ans = float("inf")
    for i in range(1, 41):
        t = (ma*i, mb*i)
        if t in dp[n]:
            if ans > dp[n][t]:
                ans = dp[n][t]
    if ans == float("inf"):
        print("-1")
    else:
        print(ans)

def __starting_point():
    main()
__starting_point()

import copy
n, ma, mb = map(int, input().split())
a, b, c = [0]*n, [0]*n, [0]*n
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
   
dp = [[float('inf')] * (sum(b)+1) for _ in range(sum(a)+1)]
dp[0][0] = 0
step = set([(0, 0)])

for i in range(n):
    ai, bi = a[i], b[i]

    s = step.copy()
    tempdp = copy.deepcopy(dp)
    for si in s: 
        if dp[si[0]+ai][si[1]+bi] > dp[si[0]][si[1]] + c[i]:
            tempdp[si[0]+ai][si[1]+bi] = dp[si[0]][si[1]] + c[i]
            step.add((si[0]+ai, si[1]+bi))
        
    dp = tempdp[:]
#28 20

ans = float('inf')
for i in range(1, min(sum(a)//ma, sum(b)//mb)+1):
    ans = min(ans, dp[ma*i][mb*i])
    
if ans == float('inf'): print(-1)
else : print(ans)

import numpy as np

n,ma,mb=map(int,input().split())
L=10*n

dp=np.zeros((L+1,L+1),dtype="int64")
dq=np.zeros((L+1,L+1),dtype="int64")

inf=10**18
dp+=inf
dp[0][0]=0

for i in range(n):
    a,b,c=map(int,input().split())
    dq=dp.copy()
    dq[a:,b:]=np.minimum(dq[a:,b:],dp[:-a,:-b]+c)
    dp=dq
    
ans=inf
for i in range(1,401):
    if ma*i > L or mb*i > L:
        break
    ans=min(ans,dp[ma*i][mb*i])
if ans==inf:
    print(-1)
else:
    print(ans)

N, Ma, Mb = list(map(int, input().split()))
D = [tuple(map(int, input().split())) for _ in range(N)]

def listup(L, D):
    for a, b, c in D:
        for (ka, kb), kc in L.copy().items():
            key = (ka+a, kb+b)
            L[key] = min(L[key], kc+c) if key in L else kc+c
        

L1 = {(0,0):0}
L2 = {(0,0):0}
listup(L1, D[:N//2])
listup(L2, D[N//2:])

ans = 10**9
for m in range(1,401):
    ma = Ma * m
    mb = Mb * m
    if ma>400 or mb>400: break
    for key1 in L1:
        ta1, tb1 = key1
        ta2 = ma - ta1
        tb2 = mb - tb1
        key2 = (ta2, tb2)
        if key2 in L2: ans = min(ans, L1[key1]+L2[key2])

print(ans if ans!=10**9 else -1)

n,ma,mb=list(map(int,input().split()))
abc=[]
for i in range(n):
    abc.append([int(j) for j in input().split()])
from operator import itemgetter
abc.sort(key=itemgetter(2))

dp=[[10**18 for i in range(401)]for j in range(401)]
dp[0][0]=0

p,q=0,0
for a,b,c in abc:
    for j in reversed(list(range(q+1))):
        for i in range(p+1):
            if dp[i][j]==10**18:
                continue
            else:
                dp[i+a][j+b]=min(dp[i+a][j+b],dp[i][j]+c)
    p+=a
    q+=b

ans=1145141919
i=1
while ma*i<401 and mb*i<401:
    ans=min(ans,dp[ma*i][mb*i])
    i+=1
if ans==1145141919:
    print((-1))
else:
    print(ans)





N,Ma,Mb=map(int, input().split())
A = []
B = []
C = []
for i in range(N):
  a,b,c=map(int, input().split())
  A.append(a)
  B.append(b)
  C.append(c)
sa = sum(A)
sb = sum(B)

dp = [[[10000]*(sb+1) for _ in range(sa+1)] for _ in range(N+1)]
dp[0][0][0] = 0

ta = 0
tb = 0
for i in range(N):
  a = A[i]
  b = B[i]
  for j in range(sa):
    for k in range(sb):
      if j - a >= 0 and k - b >= 0:
        dp[i+1][j][k] = min(dp[i][j-a][k-b]+C[i], dp[i][j][k])
      else:
        dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

ans = 10000
for i in range(1, sa+1):
  for j in range(1, sb+1):
    if Ma * j == Mb * i:
      ans = min(ans, dp[N][i][j])
if ans == 10000:
  ans = -1
print(ans)

import numpy as np
N, ma, mb = list(map(int, input().split()))
abc = tuple(list(map(int, input().split())) for _ in range(N))

inf = 10000
dp = np.full((401, 401), inf, dtype=int)
dp[0][0] = 0

for a, b, c in abc:
    for i in range(400, a - 1, -1):
        dp[i][b:] = np.minimum(dp[i][b:], dp[i - a][: - b] + c)

ans = inf
x = 1

while True:
    Ma = x * ma
    Mb = x * mb
    if Ma > 400 or Mb > 400:
        break
    ans = min(ans, dp[Ma][Mb])
    x += 1

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


import sys

read = sys.stdin.readline
N, Ma, Mb = list(map(int, read().split()))
abc = [tuple(map(int, read().split())) for _ in range(N)]
d = [(Mb * a - Ma * b, c) for a, b, c in abc]
dic = dict()
for i, j in d:
    for key, value in tuple(dic.items()):
        n = key + i
        if dic.get(n):
            dic[n] = min(value + j, dic[n])
        else:
            dic[n] = value + j
    if dic.get(i):
        dic[i] = min(j, dic[i])
    else:
        dic[i] = j

if dic.get(0):
    print((dic[0]))
else:
    print((-1))


from collections import defaultdict

N, Ma, Mb = list(map(int, input().split()))
M = [tuple(map(int, input().split())) for _ in range(N)]

d = defaultdict(lambda: float('inf'))
d[(0, 0)] = 0
for a, b, c in M:
    new_d = d.copy()
    for key_a, key_b in d:
        new_d[(a + key_a, b + key_b)] = min(new_d[(a + key_a, b + key_b)],
                                            d[(key_a, key_b)] + c)
    d = new_d

ans = float('inf')
for i in range(1, 401 // max(Ma, Mb)):
    ans = min(ans, d[(Ma * i, Mb * i)])
print((ans if ans != float('inf') else -1))


# A,Bそれぞれの最大値は40 * 10である
# dp[i][j] = Aがiグラム、Bがjグラム含まれた薬品の最小コスト

import sys
readline = sys.stdin.readline

N,Ma,Mb = map(int,readline().split())
INF = 10 ** 10
dp = [[INF] * (401) for i in range(401)]
dp[0][0] = 0

for _ in range(N):
  a,b,c = map(int,readline().split())
  for i in range(len(dp) - 1, -1, -1):
    for j in range(len(dp[i]) - 1, -1, -1):
      if dp[i][j] == INF:
        continue
      dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)

ans = INF
import math
for i in range(1, len(dp)):
  for j in range(1, len(dp)):
    g = math.gcd(i,j)
    if i // g == Ma and j // g == Mb:
      if ans > dp[i][j]:
        ans = dp[i][j]
      
if ans == INF:
  print(-1)
else:
  print(ans)

N,A,B = map(int,input().split())
X = [1<<20]*4040

for n in range(N):
  a,b,c = map(int,input().split())
  t = A*b-B*a
  X = [min(X[m],(0 if (m-t)%4040==0 else X[(m-t)%4040])+c) for m in range(4040)]

if 1<<18<X[0]:
  print(-1)
else:
  print(X[0])

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

INF = 10000

dp = [[INF for b in range(401)] for a in range(401)]

dp[0][0] = 0

sum_a = 0
sum_b = 0

for i in range(1,N+1):
    ai,bi,ci = list(map(int,input().split()))
    sum_a += ai
    sum_b += bi
    for a in range(sum_a+1,-1,-1):
        for b in range(sum_b+1,-1,-1):
            if a-ai >= 0 and b-bi >= 0:
                dp[a][b] = min(dp[a][b],dp[a-ai][b-bi]+ci)


ans = INF
for j in range(1,401):
    if Ma*j > 400 or Mb*j > 400:
        break
    ans = min(ans,dp[Ma*j][Mb*j])
print((ans if ans != INF else -1))


def main():
	n, ma, mb, *L = 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)

def __starting_point():
	main()
__starting_point()

N, Ma, Mb = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for _ in range(N)]
ABC.sort(key=lambda x: x[2])

dp = [[(0, 0, [-1])]]

for p in range(1, N * 100 + 1):
    tmp = []
    for i, (a, b, c) in enumerate(ABC):
        if p - c >= 0:
            for ta, tb, ti in dp[p - c]:
                if ti[-1] < i:
                    if (a + ta) * Mb == (b + tb) * Ma:
                        print(p)
                        return
                    tmp.append((a + ta, b + tb, ti + [i]))
    dp.append(tmp)

print("-1")


N, Ma, Mb = list(map(int, input().split()))
L = []
sum_a = 0
sum_b = 0
for _ in range(N):
    a, b, c = list(map(int, input().split()))
    sum_a += a
    sum_b += b
    L.append((a, b, c))

inf = 10 ** 9 + 7
dp = [[[inf] * (sum_b + 1) for _ in range(sum_a + 1)] for _ in range(N + 1)]

dp[0][0][0] = 0
for i in range(N):
    for a in range(sum_a + 1):
        for b in range(sum_b + 1):
            if 0 <= a - L[i][0] and 0 <= b - L[i][1]:
                # print(a, b, L[i])
                dp[i + 1][a][b] = min(dp[i][a - L[i][0]]
                                      [b - L[i][1]] + L[i][2], dp[i][a][b])
            else:
                dp[i + 1][a][b] = dp[i][a][b]

min_cost = inf
for a in range(sum_a + 1):
    for b in range(sum_b + 1):
        if a * Mb == b * Ma and dp[N][a][b] != 0:
            # print(a, b, dp[N][a][b])
            min_cost = min(dp[N][a][b], min_cost)

print((min_cost if min_cost != inf else -1))


INF = float('inf')
n, ma, mb = list(map(int, input().split()))
t = [[INF] * 401 for _ in range(401)]
t[0][0] = 0
for _ in range(n):
  a, b, c = list(map(int, input().split()))
  for aa in range(400, -1, -1):
    for bb in range(400, -1, -1):
      if t[aa][bb] == INF:
        continue
      if t[a + aa][b + bb] > t[aa][bb] + c:
        t[a + aa][b + bb] = t[aa][bb] + c
result = INF
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == INF:
  result = -1
print(result)


n,ma,mb = map(int,input().split())
med = [tuple(map(int,input().split())) for _ in range(n)]
maa = sum(x[0] for x in med)
mab = sum(x[1] for x in med)
dp = [[10**6]*(mab+1) for _ in range(maa+1)]
dp[0][0] = 0
for a,b,c in med:
  for i in range(maa,a-1,-1):
    for j in range(mab,b-1,-1):
      if dp[i][j] > dp[i-a][j-b] + c:
        dp[i][j] = dp[i-a][j-b] + c
mi = min(dp[ma*i][mb*i] for i in range(1,min(maa//ma,mab//mb)+1))
if mi > 10**5:
  mi = -1
print(mi)

N,MA,MB = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(N)]

from collections import defaultdict
from copy import copy
d = defaultdict(lambda: float('inf'))
d[(0,0)] = 0
for a,b,c in ABC:
    d2 = copy(d)
    for (pa,pb),pc in d.items():
        d2[(pa+a, pb+b)] = min(d2[(pa+a, pb+b)], pc+c)
    d = d2

ans = float('inf')
for (a,b),c in d.items():
    if a==b==0: continue
    if a*MB == b*MA:
        ans = min(ans, c)
print(-1 if ans==float('inf') else ans)

N, Ma, Mb = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]

an = 0
bn = 0
for a, b, c in abc:
  an += a
  bn += b

ma = max(an, bn) + 1

DP = [[10 ** 10] * ma for _ in range(ma)]

for i in range(N):
  a, b, c = abc[i]
  for j in range(ma - 1, -1, -1):
    for k in range(ma - 1, -1, -1):
      if j == 0 and k == 0:
        DP[a][b] = min(DP[a][b], c)
        continue
      if DP[j][k] == 10 ** 10: continue
      if j + a >= ma or k + b >= ma: continue
      DP[j + a][k + b] = min(DP[j + a][k + b], DP[j][k] + c)

ans = 10 ** 10
a, b = Ma, Mb
while a < ma and b < ma:
  ans = min(ans, DP[a][b])
  a += Ma
  b += Mb

if ans == 10 ** 10:
  print((-1))
else:
  print(ans)


import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,ma,mb=MI()
    inf=10**9
    abc=[LI() for _ in range(n)]
    dp=[[[inf]*(n*10+1) for _ in range(10*n+1)] for _ in range(n+1)]
    dp[0][0][0]=0
    for i,(a,b,c) in enumerate(abc):
        for j in range(n*10+1):
            for k in range(n*10+1):
                pre=dp[i][j][k]
                if pre==inf:continue
                dp[i+1][j][k]=min(dp[i+1][j][k],pre)
                dp[i+1][j+a][k+b]=min(dp[i+1][j+a][k+b],pre+c)
    ans=inf
    for i in range(1,105):
        a=i*ma
        b=i*mb
        if a>n*10 or b>n*10:break
        ans=min(ans,dp[n][a][b])
    if ans==inf:print(-1)
    else:print(ans)

main()

import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, ma, mb = I[:3]
abc = I[3:].reshape(n, 3)

def main():
    sa, sb = np.sum(abc, axis=0)[:2]
    res = np.full((sa+1, sb+1), np.inf)
    res[0, 0] = 0

    for a, b, c in abc:
        res[a:, b:] = np.minimum(res[a:, b:], res[:-a, :-b] + c)
    
    a = np.arange(ma, sa+1, ma)
    b = np.arange(mb, sb+1, mb)
    lim = min(sa//ma, sb//mb)
    ans = np.amin(res[a[:lim], b[:lim]])
    
    if ans == np.inf:
        return -1
    return int(ans)

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

n,ma,mb=list(map(int,input().split()))
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)
sa1=sa+1
sb1=sb+1

inf=10000000000
x=[[inf]*(sb1) for i in range(sa1)]
x[0][0]=0
for i in range(n):
    now=el[i]
    x_sub=[[0]*(sb1) for i in range(sa1)]
    for k in range(sa1):
        for l in range(sb1):
            if x[k][l]!=inf:
                if k+now[0]<sa1:
                    if l+now[1]<sb1:
                        x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    for k in range(sa1):
        for l in range(sb1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print((-1))
else:
    print(ans)


N, Ma, Mb = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(N)]
INF = float("inf")
DP = [[[INF] * (11*N+1) for _ in range(11*N+1)] for _ in range(N+1)]
DP[0][0][0] = 0
for i, (a, b, c) in enumerate(ABC):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if DP[i][j][k] == INF: continue
            DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
            DP[i+1][j+a][k+b] = min(DP[i+1][j+a][k+b], DP[i][j][k] + c)
ans = INF
for j in range(1,10*N+1):
    for k in range(1,10*N+1):
        if Ma * k == Mb * j:
            ans = min(ans, DP[N][j][k])
if ans == INF:
    ans = -1
print(ans)

INF = float("inf")

N, Ma, Mb, *ABC = map(int, open(0).read().split())

M = 160010

dp = [0] + [INF] * M
for a, b, c in zip(*[iter(ABC)] * 3):
    T = dp[:]
    p = 401 * a + b
    for i, dpi in enumerate(dp):
        j = p + i
        if j > M:
            break
        if T[j] > dpi + c:
            T[j] = dpi + c
    dp = T

ans = INF
for i in range(1, M):
    a, b = divmod(i, 401)
    if Ma * b == Mb * a and ans > dp[i]:
        ans = dp[i]

print(-1 if ans == INF else ans)

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

sum_a = 0
sum_b = 0
A = []
B = []
C = []
for _ in range(N):
    a, b, c = list(map(int, input().split()))
    sum_a += a
    sum_b += b
    A.append(a)
    B.append(b)
    C.append(c)

inf = 10 ** 9 + 7
# 3次元dpを考える
dp = [[[inf] * (sum_b + 1) for _ in range(sum_a + 1)] for _ in range(N + 1)]

dp[0][0][0] = 0
for i in range(N):
    for sa in range(sum_a):
        for sb in range(sum_b):
            if sa - A[i] >= 0 and sb - B[i] >= 0:
                dp[i + 1][sa][sb] = min(dp[i][sa - A[i]]
                                        [sb - B[i]] + C[i], dp[i][sa][sb])
            else:
                dp[i + 1][sa][sb] = min(dp[i][sa][sb], dp[i + 1][sa][sb])

ans = inf
for i in range(1, sum_a + 1):
    for j in range(1, sum_b + 1):
        if Ma * j == Mb * i:
            ans = min(ans, dp[N][i][j])

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


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

MA=sum(a)
MB=sum(b)
dp=[[[float("inf") for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0]=0
for i in range(N):
    for j in range(MA):
        for k in range(MB):
            if dp[i][j][k]==float("inf"):
                continue
            dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
            dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])

ans=float("inf")
for i in range(1,MA+1):
    for j in range(1,MB+1):
        if i*mb==j*ma:
            ans=min(ans,dp[N][i][j])

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

n, ma, mb = list(map(int, input().split()))
r = [0] * n
c = [0] * n
for i in range(n):
  a, b, c[i] = list(map(int, input().split()))
  r[i] = a * mb - b * ma
dp = [[10 ** 9] * 4001 for i in range(n + 1)]
for i in range(n):
  for j in range(4001):
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    if j == 2000:
      dp[i+1][j+r[i]] = min(dp[i+1][j+r[i]], c[i])
    if 0 <= j + r[i] <= 4000:
      dp[i+1][j+r[i]] = min(dp[i+1][j+r[i]], dp[i][j] + c[i])
if dp[n][2000] < 10 ** 9:
  print((dp[n][2000]))
else:
  print((-1))


N,Ma,Mb=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]=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))

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,Ma,Mb = list(map(int,input().split()))
    abc = [list(map(int,input().split())) for i in range(N)]

    INF = N * 100 + 1

    dp = [[[INF for cb in range(411)] for ca in range(411)] for i in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for ca in range(N*10):
            for cb in range(N*10):
                if dp[i][ca][cb] == INF:
                    continue
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb],dp[i][ca][cb])
                d = abc[i]
                dp[i+1][ca+d[0]][cb+d[1]] = min(dp[i+1][ca+d[0]][cb+d[1]],dp[i][ca][cb]+d[2])

    res = INF

    for ca in range(1,401):
        for cb in range(1,401):
            if ca * Mb == cb * Ma:
                res = min(res,dp[N][ca][cb])

    if res == INF:
        res = -1

    print(res)



main()


def main():
    N, Ma, Mb = map(int, input().split())
    yakuhin = []
    sa = 0
    sb = 0
    for i in range(N):
        yakuhin.append(list(map(int, input().split())))
        sa += yakuhin[i][0]
        sb += yakuhin[i][1]
    
    INF = 10**15
    DP = [[[INF for _ in range(sb+1)] for _ in range(sa+1)] for _ in range(N+1)]
    
    for i in range(N):
        DP[i][0][0] = 0
    
    for i in range(N):
        for j in range(sa+1):
            for k in range(sb+1):
                if(j >= yakuhin[i][0] and k >= yakuhin[i][1]):
                    DP[i+1][j][k] = min(DP[i][j][k], DP[i][j-yakuhin[i][0]][k-yakuhin[i][1]]+yakuhin[i][2])
                else:
                    DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
        
    ans = INF
    for i in range(1, N+1):
        for j in range(1, sa+1):
            for k in range(1, sb+1):
                if(j*Mb == k*Ma):
                    ans = min(ans, DP[i][j][k])    
        
    print(ans if ans != INF else -1)
    
main()

import sys
import numpy as np
from collections import deque,defaultdict

inp=lambda v,w:v[0]*w[0]+v[1]*w[1]
isprop = lambda a,b: a[0]*b[1]==a[1]*b[0]
cwsum = lambda l:[sum([x[0] for x in l]), sum([x[1] for x in l])]
chmin = lambda a,b:(a,b)[b<a]
# cwsum = lambda l:np.sum(l,axis=0)
            
def main():
    N,Ma,Mb=list(map(int,input().split()))
    infty=10**9
    ch=[list(map(int,input().split())) for _ in range(N)]
    p=[(-1)*Mb,Ma]
    # cand=[v[2] for v in ch if inp(p,v[:2])==0]
    # if cand:
        # m1=min(cand)
    # else:
        # m1=infty
    # ncand=[v for v in ch if inp(p,v[:2])!=0] #p方向への射影
    pch=[[inp(v[:2],p),v[2]] for v in ch]
    X=N*max([abs(w[0]) for w in pch])
    dp=[[infty]*(2*X+1) for _ in range(N)]
    for i in range(N):
        for j in range(2*X+1):
            if i==0 and j==X+pch[0][0]:
                dp[i][j]=pch[0][1]
            elif i>0 and j==X+pch[i][0]:
                dp[i][j]=chmin(dp[i-1][j],pch[i][1])
            elif i>0 and j>=pch[i][0] and j<=2*X+pch[i][0]:
                dp[i][j]=chmin(dp[i-1][j],dp[i-1][j-pch[i][0]]+pch[i][1])
            elif i>0:
                dp[i][j]=dp[i-1][j]
    #  print(ch)
    #  print(pch)
    #  print(dp)
    if dp[N-1][X]==infty:
        print((-1))
    else:
        print((dp[N-1][X]))

def __starting_point():
    main()

__starting_point()

INF = float('inf')

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

cmax = N * 10
t = [[INF] * (cmax + 1) for _ in range(cmax + 1)]
for _ in range(N):
    a, b, c = list(map(int, input().split()))
    for aa in range(cmax, 0, -1):
        for bb in range(cmax, 0, -1):
            if t[aa][bb] == INF:
                continue
            t[aa + a][bb + b] = min(t[aa + a][bb + b], t[aa][bb] + c)
    t[a][b] = min(t[a][b], c)

result = INF
for a in range(1, cmax):
    for b in range(1, cmax):
        if a * Mb == b * Ma:
            result = min(result, t[a][b])
if result == INF:
    result = -1
print(result)


N,Ma,Mb=list(map(int,input().split()))
ABC=[tuple(map(int,input().split())) for i in range(N)]
inf=float("inf")
DP=[[inf]*401 for i in range(401)]
DP[0][0]=0
for a,b,c in ABC:
   for i in reversed(range(401)):
      for j in reversed(range(401)):
         if DP[i][j]!=inf:
            DP[i+a][j+b]=min(DP[i][j]+c,DP[i+a][j+b])
ans=inf
for i in range(1,401):
   for j in range(1,401):
      if Ma*j==Mb*i:
         ans=min(ans,DP[i][j])
print(-1 if ans==inf else ans)

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

INF = float('inf')

dp = [[INF for b in range(401)] for a in range(401)]

dp[0][0] = 0

sa = 0
sb = 0

for i in range(1,N+1):
    ai,bi,ci = list(map(int,input().split()))
    sa += ai
    sb += bi
    for a in range(sa+1,-1,-1):
        for b in range(sb+1,-1,-1):
            if a-ai >= 0 and b-bi >= 0:
                dp[a][b] = min(dp[a][b],dp[a-ai][b-bi]+ci)


ans = INF
for j in range(1,401):
    if Ma*j > 400 or Mb*j > 400:
        break
    ans = min(ans,dp[Ma*j][Mb*j])
print((ans if ans != INF else -1))



n,ma,mb=list(map(int,input().split()))
item=[]
for i in range(n):
  item.append(tuple(map(int,input().split())))

d={(0,0):0}
for i in range(n):
  nd={}
  for j in d:
    if j in nd:
      nd[j]=min(nd[j],d[j])
    else:
      nd[j]=d[j]
    s=(j[0]+item[i][0],j[1]+item[i][1])
    if s in nd:
      nd[s]=min(nd[s],d[j]+item[i][2])
    else:
      nd[s]=d[j]+item[i][2]
  d=nd
m=10**9
for i in d:
  if i==(0,0):
    continue
  if i[0]*mb==i[1]*ma:
    m=min(m,d[i])
if m==10**9:
  m=-1

print(m)

INF = float('inf')
n, ma, mb = list(map(int, input().split()))
ccmax = n * 10
t = [[INF] * (ccmax + 1) for _ in range(ccmax + 1)]
for _ in range(n):
  a, b, c = list(map(int, input().split()))
  for aa in range(ccmax, 0, -1):
    taa = t[aa]
    for bb in range(ccmax, 0, -1):
      if taa[bb] == INF:
        continue
      if t[a + aa][b + bb] > c + taa[bb]:
        t[a + aa][b + bb] = c + taa[bb]
  if t[a][b] > c:
    t[a][b] = c
result = INF
for a in range(1, ccmax):
  ta = t[a]
  for b in range(1, ccmax):
    if a * mb == b * ma and ta[b] < result:
      result = ta[b]
if result == INF:
  result = -1
print(result)


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

INF = 10 ** 8

lst = [[INF] * 401 for i in range(401)]
lst[0][0] = 0

for _ in range(N):
    a, b, c = list(map(int, input().split()))
    for i in range(400, a - 1, -1):
        for j in range(400, b - 1, -1):
            if lst[i- a][j - b] == INF:
                pass
            else:
                lst[i][j] = min(lst[i][j], lst[i - a][j - b] + c)

ans = INF
n = 400 // max(Ma, Mb)
for i in range(1, n + 1):
    ans = min(ans, lst[Ma * i][Mb * i])

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

# for i in range(7):
#     print (lst[i][:7])


import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, ma, mb = I[:3]
abc = I[3:].reshape(n, 3)

def main():
    sa, sb = np.sum(abc, axis=0)[:2]
    res = np.full((sa+1, sb+1), np.inf)
    res[0, 0] = 0

    for a, b, c in abc:
        res[a:, b:] = np.minimum(res[a:, b:], res[:-a, :-b] + c)
    
    ans = np.inf
    for i in range(1, min(sa//ma, sb//mb) + 1):
        ans = np.minimum(ans, res[ma * i, mb * i])
    
    if ans == np.inf:
        return -1
    return int(ans)
    
def __starting_point():
    ans = main()
    print(ans)
__starting_point()

import sys
import numpy as np
input = sys.stdin.readline

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

    INF = int(1e6)
    MAX = (N+1) * 10 + 1
    dp = np.full((MAX, MAX), INF, dtype=np.int64)
    tmp = np.zeros_like(dp)

    dp[0][0] = 0
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        tmp = dp.copy()
        tmp[a:, b:] = np.minimum(tmp[a:, b:], dp[:-a, :-b] + c)
        dp = tmp
    
    ans = INF
    a, b = Ma, Mb
    while a < MAX and b < MAX:
        ans = min(ans, dp[a][b])
        a += Ma
        b += Mb
    
    if ans == INF:
        ans = -1
    
    print(ans)

def __starting_point():
    main()

__starting_point()

inf=10**10
n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(n)]
memo=[[inf]*401 for _ in range(401)]
memo[0][0]=0
for a,b,c in abc:
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if memo[i][j]!= inf :
        memo[i+a][j+b]= min(memo[i+a][j+b], memo[i][j] + c)


ans=inf
for i in range(1,min(400//ma,400//mb)):
  ans=min(ans, memo[ma*i][mb*i])

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

N,Ma,Mb=map(int,(input().split()))
a,b,c=[0]*N,[0]*N,[0]*N

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

MA=sum(a)
MB=sum(b)
dp=[[[float("inf") for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0]=0
for i in range(N):
  for j in range(MA):
    for k in range(MB):
      if dp[i][j][k]==float("inf"):
        continue
      dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
      dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])

ans=float("inf")
for i in range(1,MA+1):
  for j in range(1,MB+1):
    if i*Mb==j*Ma:
      ans=min(ans,dp[N][i][j])

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

import copy

N, Ma, Mb = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for _ in range(N)]

INF, W = 10000, 10 * max(Ma, Mb) * N
dp = [[INF] * (2 * W + 1)]

for a, b, c in ABC:
    dp.append(copy.deepcopy(dp[-1]))
    df = a * Mb - b * Ma
    dp[-1][df] = min(dp[-1][df], c)
    for d in range(-W, W + 1):
        dp[-1][df + d] = min(dp[-1][df + d], c + dp[-2][d])

print(("-1" if dp[N][0] == INF else dp[N][0]))


def main():
    N, Ma, Mb = map(int, input().split())
    yakuhin = []
    for i in range(N):
        yakuhin.append(list(map(int, input().split())))
    
    INF = 10**15
    DP = [[[INF for _ in range(401)] for _ in range(401)] for _ 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] != INF):
                    DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
                    DP[i+1][j+yakuhin[i][0]][k+yakuhin[i][1]] = min(DP[i+1][j+yakuhin[i][0]][k+yakuhin[i][1]], DP[i][j][k]+yakuhin[i][2])
    
    ans = INF
    for i in range(1, N+1):
        for j in range(1, 401):
            for k in range(1, 401):
                if(j*Mb == k*Ma):
                    ans = min(ans, DP[i][j][k])    
        
    print(ans if ans != INF else -1)
    
main()

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,Ma,Mb = map(int,input().split())
ABC = [tuple(map(int,input().split())) for _ in range(N)]

# dp[a][b] : Aタイプが ag, Bタイプが bg となる 最小コスト
inf = float("inf")
dp = [[inf for _ in range(401)] for _ in range(401)]
dp[0][0] = 0

for a,b,c in ABC:
    for i in range(400,-1,-1):
        for j in range(400,-1,-1):
            if dp[i][j] != inf:
                # 薬品を使った方が安ければ更新する
                dp[i+a][j+b] = min(dp[i+a][j+b], dp[i][j] + c)

ans = inf
for i in range(1,401):
    for j in range(1,401):
        # i : j == Ma : Mb なら コストを更新
        if i*Mb == j*Ma:
            ans = min(ans, dp[i][j])

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

N,Ma,Mb = map(int,input().split())
Data = []
for _ in range(N):
    a,b,c = map(int,input().split())
    Data.append([a,b,c])

DP = []
for _ in range(N+1):
    temp = [[-1]*(N*10+1) for _ in range(N*10+1)]
    DP.append(temp)
DP[0][0][0] = 0

for i in range(1,N+1):
    A,B,C = Data[i-1]
    for a in range(0,N*10+1):
        for b in range(0,N*10+1):
            if DP[i-1][a][b] != -1:
                # 使わない
                if DP[i][a][b] == -1:
                    DP[i][a][b] = DP[i-1][a][b]
                else:
                    DP[i][a][b] = min(DP[i][a][b],DP[i-1][a][b])

                #使う
                if DP[i][a+A][b+B] == -1:
                    DP[i][a+A][b+B] = DP[i-1][a][b]+C
                else:
                    DP[i][a+A][b+B] = min(DP[i][a+A][b+B],DP[i-1][a][b]+C)
ans = -1
for a in range(1,N*10+1):
    for b in range(1,N*10+1):
        if DP[N][a][b] != -1 and a * Mb == b * Ma:
            if ans == -1:
                ans = DP[N][a][b]
            else:
                ans = min(ans,DP[N][a][b])
print(ans)

import sys



n, ma, mb = map(int, input().split())
abc = []

for _ in range(n):
    a, b, cost = map(int, input().split())
    abc.append((a, b, cost))

def main():
    sa = 0
    sb = 0
    for i in range(n):
        sa += abc[i][0]
        sb += abc[i][1]

    res = [[float('infinity')] * (sb + 1) for _ in range(sa + 1)]
    res[0][0] = 0

    for a, b, c in abc:

        for j in range(sa, -1, -1):
            for k in range(sb, -1, -1):
                if j >= a and k >= b:
                    res[j][k] = min(res[j][k], res[j-a][k-b] + c)

    ans = float('infinity')
    for i in range(1, min(sa//ma, sb//mb) + 1):
        ans = min(ans, res[ma*i][mb*i])

    if ans == float('infinity'):
        return -1
    else:
        return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

# 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))


def __starting_point():
    main()

__starting_point()

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

kusuri = []
cusum = [0]*(N+1)
for i in range(N):
  a, b, c = map(int, input().split())
  sa = a*Mb - b*Ma
  kusuri.append((sa, c))
  cusum[i+1] = cusum[i] + c

call = cusum[-1]
dp = [[call+1]*8001 for _ in range(41)]
dp[0][4000] = 0

cmin = call+1
for i, j in enumerate(kusuri):
  d = j[0]
  c = j[1]
  for k in range(4000-100*i, 4000+100*i+1):
    dp[i+1][k] = min(dp[i+1][k], dp[i][k])
    if k + d == 4000:
      cmin = min(cmin, dp[i][k]+c)
    dp[i+1][k+d] = min(dp[i+1][k+d], dp[i][k]+c)
    

if cmin == call+1:
  print(-1)
else:
  print(cmin)

import sys

INF = float('inf')

n, ma, mb = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = list(zip(*[abc] * 3))

def main():
    sa = 0
    sb = 0
    for i in range(n):
        sa += abc[i][0]
        sb += abc[i][1]

    res = [[INF] * (sb + 1) for _ in range(sa + 1)]
    res[0][0] = 0

    for a, b, c in abc:

        for j in range(sa, -1, -1):
            for k in range(sb, -1, -1):
                if j >= a and k >= b:
                    res[j][k] = min(res[j][k], res[j-a][k-b] + c)

    ans = INF
    for i in range(1, min(sa//ma, sb//mb) + 1):
        ans = min(ans, res[ma*i][mb*i])

    if ans == INF:
        return -1
    else:
        return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

n,ma,mb = map(int,input().split())

INF = 10**4
dp = [[[INF] * (n*10+1) for _ in range(n*10+1)] for _ in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    a,b,c = map(int,input().split())
    for ai in range(i*10+11):
        for bi in range(i*10+11):
            if ai>=a and bi>=b:
                tmp = dp[i][ai-a][bi-b] + c
            else:
                tmp = INF
            dp[i+1][ai][bi] = min(dp[i][ai][bi], tmp)

ans = min(dp[n][ma*i][mb*i] for i in range(1,n*10//max(ma,mb)+1) )
if ans == INF: ans = -1
    
print(ans)

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)

import numpy as np
n, ma, mb = map(int, input().split())
r = 10 * n + 6
inf = 10**5
dp = np.full((n+1, r, r), inf)
dp[0][0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    dp[i+1][a:, b:] = np.minimum(
        dp[i][:r-a, :r-b] + c, dp[i][a:, b:]
    )
    dp[i+1] = np.minimum(dp[i+1], dp[i])

ans = inf
x, y = 0, 0
while True:
    x += ma
    y += mb
    if x < r and y < r:
        ans = min(ans, dp[n][x][y])
    else:
        break
if ans == inf:
    print(-1)
else:
    print(int(ans))