AtCoder Beginner Contest 054 - Mixing Experiment

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: MEDIUM

Starter code:

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


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


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


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)


import sys
sys.setrecursionlimit(10 ** 8)
(N, Ma, Mb) = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = {i: {} for i in range(N)}

def dfs(i, a, b):
	if b > 0 and a / b == Ma / Mb:
		return 0
	elif i == N:
		return float('inf')
	elif (a, b) in memo[i]:
		return memo[i][a, b]
	else:
		ans = min(dfs(i + 1, a, b), dfs(i + 1, a + A[i][0], b + A[i][1]) + A[i][2])
	memo[i][a, b] = ans
	return ans
if dfs(0, 0, 0) == float('inf'):
	print(-1)
else:
	print(dfs(0, 0, 0))


(n, ma, mb) = map(int, input().split())
ab = [[[10 ** 6] * 401 for _ in range(401)] for _ in range(n + 1)]
ab[0][0][0] = 0
for p in range(1, n + 1):
	(a, b, c) = map(int, input().split())
	for i in range(400):
		for j in range(400):
			ab[p][i][j] = min(ab[p][i][j], ab[p - 1][i][j])
			if i + a <= 400 and j + b <= 400:
				ab[p][i + a][j + b] = min(ab[p][i + a][j + b], ab[p - 1][i][j] + c)
ans = 10 ** 6 - 1
for i in range(401):
	for j in range(401):
		if i != 0 and j != 0:
			if i * mb == j * ma:
				ans = min(ans, ab[n][i][j])
if ans == 10 ** 6 - 1:
	print(-1)
else:
	print(ans)


mod = 1777777777
(n, ma, mb) = map(int, input().split())
d = [[mod for j in range(100)] for i in range(100)]
for i in range(n):
	(a, b, c) = map(int, input().split())
	x = a
	y = b
	for j in range(100 - a - 1, 0, -1):
		for k in range(100 - b - 1, 0, -1):
			if d[j][k] != mod:
				d[j + a][k + b] = min(d[j + a][k + b], d[j][k] + c)
	d[x][y] = min(d[x][y], c)
ans = mod
for i in range(100):
	if i % ma == 0 and mb * i // ma < 100:
		ans = min(ans, d[i][mb * i // ma])
print([ans, -1][ans == mod])


import copy
LI = lambda : list(map(int, input().split()))
(N, Ma, Mb) = LI()
ABC = [LI() for _ in range(N)]
INF = 10 ** 5

def main():
	w = [[INF] * 401 for _ in range(401)]
	w[0][0] = 0
	for (a, b, c) in ABC:
		l = copy.deepcopy(w)
		for j in range(a, 401):
			for k in range(b, 401):
				l[j][k] = min(w[j][k], w[j - a][k - b] + c)
		w = l
	ans = INF
	n = 400 // max(Ma, Mb) + 1
	for i in range(1, n):
		ans = min(ans, w[Ma * i][Mb * i])
	ans = -1 if ans == INF else ans
	print(ans)
main()


(N, Ma, Mb) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(N)]
INF = 10 ** 5
n = 10 * N + 1
dp = [[[INF] * n for i in range(n)] for j in range(N + 1)]
dp[0][0][0] = 0
for (i, (a, b, c)) in enumerate(abc, 1):
	for j in range(n):
		for k in range(n):
			dp[i][j][k] = dp[i - 1][j][k]
			if a <= j and b <= k:
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - a][k - b] + c)
ans = INF
dp[-1][0][0] = INF
for j in range(n):
	for k in range(n):
		if j * Mb == k * Ma:
			ans = min(ans, dp[-1][j][k])
if ans < INF:
	print(ans)
else:
	print(-1)


(n, ma, mb) = map(int, input().split())
r = [0] * n
c = [0] * n
for i in range(n):
	(a, b, c[i]) = 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())
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
input = sys.stdin.buffer.readline
(n, ma, mb) = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(n)]
infi = 10 ** 15
dp = [[[infi] * 401 for _ in range(401)] for _ in range(41)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = ABC[i]
	for j in range(401 - a):
		for k in range(401 - b):
			ni = i + 1
			nj = j + a
			nk = k + b
			dp[ni][j][k] = min(dp[ni][j][k], dp[i][j][k])
			dp[ni][nj][nk] = min(dp[i][j][k] + c, dp[ni][nj][nk])
ans = infi
for i in range(1, 401):
	if ma * i > 400:
		break
	if mb * i > 400:
		break
	ans = min(ans, dp[n][ma * i][mb * i])
print(ans if ans != infi else -1)


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


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


INF = 10 ** 10
(n, ma, mb) = map(int, input().split())
dp = [[[INF] * 500 for i in range(500)] for i in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for w_a in range(500):
		for w_b in range(500):
			dp[i + 1][w_a][w_b] = dp[i][w_a][w_b]
	for w_a in range(500):
		for w_b in range(500):
			if dp[i][w_a][w_b] == INF:
				continue
			dp[i + 1][w_a + a][w_b + b] = min(dp[i][w_a + a][w_b + b], dp[i][w_a][w_b] + c)
a = 0
b = 0
dp[n][0][0] = INF
ans = INF
while a < 500 and b < 500:
	ans = min(ans, dp[n][a][b])
	a += ma
	b += mb
if ans == INF:
	print(-1)
else:
	print(ans)


(N, A, B) = map(int, input().split())
inf = float('inf')
dp = [[inf] * 401 for _ in range(401)]
dp[0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for j in range(-1, -402, -1):
		for k in range(-1, -402, -1):
			if dp[j][k] != inf:
				dp[j + a][k + b] = min(dp[j + a][k + b], dp[j][k] + c)
ans = inf
for i in range(1, 401):
	for j in range(1, 401):
		if i / j == A / B:
			ans = min(ans, dp[i][j])
if ans == inf:
	ans = -1
print(ans)


(N, Ma, Mb) = map(int, input().split())
abc = list((list(map(int, input().split())) for i in range(N)))
DP = [[[10 ** 9] * (10 * N + 1) for i in range(10 * N + 1)] for i in range(N + 1)]
DP[0][0][0] = 0
for i in range(N):
	for j in range(10 * N + 1):
		for k in range(10 * N + 1):
			if j >= abc[i][0] and k >= abc[i][1]:
				DP[i + 1][j][k] = min(DP[i][j][k], DP[i][j - abc[i][0]][k - abc[i][1]] + abc[i][2])
			else:
				DP[i + 1][j][k] = DP[i][j][k]
ans = 10 ** 9
for i in range(1, 10 * N // max(Ma, Mb) + 1):
	ans = min(DP[-1][i * Ma][i * Mb], ans)
if ans >= 10 ** 8:
	print(-1)
else:
	print(ans)


import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools
(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)


import sys

def MI():
	return map(int, sys.stdin.readline().rstrip().split())
(N, x, y) = MI()
dp = [[[10 ** 4] * 401 for i in range(401)] for n in range(N + 1)]
dp[0][0][0] = 0
for n in range(1, N + 1):
	(a, b, c) = MI()
	for i in range(401):
		for j in range(401):
			if i >= a and j >= b:
				dp[n][i][j] = min(dp[n - 1][i][j], dp[n - 1][i - a][j - b] + c)
			else:
				dp[n][i][j] = dp[n - 1][i][j]
z = min((dp[N][x * i][y * i] for i in range(1, min(400 // x, 400 // y) + 1)))
if z == 10 ** 4:
	print(-1)
else:
	print(z)


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[:]
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)


(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(n)]
dp = [[[10000 for i in range(n * 10 + 1)] for j in range(n * 10 + 1)] for k in range(n + 1)]
for i in range(n + 1):
	dp[i][0][0] = 0
for i in range(1, n + 1):
	(x, y, c) = abc[i - 1]
	for j in range(1, n * 10 + 1):
		for k in range(1, n * 10 + 1):
			if j >= x and k >= y:
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k], dp[i - 1][j - x][k - y] + c)
			else:
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])
ans = 10000000
for i in range(1, n * 10 + 1):
	for j in range(1, n * 10 + 1):
		if i * mb == j * ma:
			ans = min(ans, dp[n][i][j])
if ans == 10000:
	print(-1)
else:
	print(ans)


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) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(n)]
wmax = 400
inf = 10 ** 10
dp = [[[inf] * (wmax + 1) for _ in range(wmax + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = abc[i]
	for j in range(wmax + 1):
		for k in range(wmax + 1):
			dp[i + 1][j][k] = dp[i][j][k]
			if j >= a and k >= b:
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j - a][k - b] + c)
ans = inf
for j in range(1, wmax + 1):
	for k in range(1, wmax + 1):
		if dp[n][j][k] >= inf:
			continue
		if ma * k == mb * j:
			ans = min(ans, dp[n][j][k])
if ans == inf:
	print(-1)
else:
	print(ans)


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


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


import copy
(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(n)]
l = 10 * n
inf = float('inf')
data = [[inf] * (l + 1) for i in range(l + 1)]
data[0][0] = 0
for u in abc:
	(a, b, c) = u
	h = copy.deepcopy(data)
	for i in range(l - a + 1):
		for j in range(l - b + 1):
			if data[i][j] != inf:
				h[i + a][j + b] = min(h[i + a][j + b], data[i][j] + c)
	data = h
k = 1
ans = inf
while ma * k <= l and mb * k <= l:
	if data[ma * k][mb * k] != inf:
		ans = min(ans, data[ma * k][mb * k])
	k += 1
if ans != inf:
	print(ans)
else:
	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]:
				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:
			min_cost = min(dp[N][a][b], min_cost)
print(min_cost if min_cost != inf else -1)


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()))
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
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())
inf = 10 ** 4
A = []
append = A.append
for i in range(n):
	(a, b, c) = map(int, input().split())
	append([a, b, c])
DP = [[[inf] * (10 * n + 1) for _ in range(10 * n + 1)] for _ in range(n + 1)]
DP[0][0][0] = 0
for i in range(n):
	(a, b, c) = (A[i][0], A[i][1], A[i][2])
	for j in range(10 * (i + 1) + 1):
		for k in range(10 * (i + 1) + 1):
			if j >= a and k >= b:
				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 = inf
for i in range(1, 10 * n + 1):
	if i * mb % ma == 0 and i * mb // ma < 10 * n + 1:
		j = i * mb // ma
		ans = min(ans, DP[n][i][j])
print(ans if ans != inf else -1)


def main():
	INF = 100 * 40 + 1
	MX = 4000
	(N, Ma, Mb) = map(int, input().split())
	dp = [[INF] * (MX * 2 + 1) for _ in range(2)]
	(i, j) = (0, 1)
	for _ in range(N):
		(ai, bi, ci) = map(int, input().split())
		x = Ma * bi - Mb * ai
		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)
main()


(n, ma, mb) = 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) = 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)


(N, Ma, Mb) = 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) = 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) = map(int, input().split())
ABC = [list(map(int, input().split())) for i in range(N)]
dp = [[[float('inf')] * (10 * N + 1) for i in range(10 * N + 1)] for j in range(N + 1)]
for i in range(N + 1):
	dp[i][0][0] = 0
for i in range(1, N + 1):
	for A in range(10 * N + 1):
		for B in range(10 * N + 1):
			(a, b, c) = ABC[i - 1]
			dp[i][A][B] = min(dp[i][A][B], dp[i - 1][A][B], c + dp[i - 1][A - a][B - b])
i = 1
ans = float('inf')
while i * Ma <= 10 * N and i * Mb <= 10 * N:
	ans = min(ans, dp[N][i * Ma][i * Mb])
	i += 1
if ans == float('inf'):
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = map(int, input().split())
L = [[float('inf')] * 410 for i in range(410)]
P = [[0, 0]]
L[0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	OldP = P.copy()
	Lsub = [L[p[0]][p[1]] for p in OldP]
	for (xp, p) in enumerate(OldP):
		if L[p[0] + a][p[1] + b] == float('inf'):
			P.append([p[0] + a, p[1] + b])
		L[p[0] + a][p[1] + b] = min(L[p[0] + a][p[1] + b], Lsub[xp] + c)
g = [Ma, Mb]
ans = float('inf')
while g[0] < 410 and g[1] < 410:
	ans = min(ans, L[g[0]][g[1]])
	g[0] += Ma
	g[1] += Mb
print(ans if ans != float('inf') 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))
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) = map(int, input().split())
dp = [[[9999] * 401 for _ in range(401)] for _ in range(n + 1)]
dp[0][0][0] = 0
sa = sb = 0
for i in range(1, n + 1):
	(a, b, c) = map(int, input().split())
	sa += a
	sb += b
	for j in range(401):
		for k in range(401):
			if j >= a and k >= b:
				dp[i][j][k] = min(dp[i - 1][j - a][k - b] + c, dp[i - 1][j][k])
			else:
				dp[i][j][k] = dp[i - 1][j][k]
a = 9999
for i in range(1, min(sa // ma, sb // mb) + 1):
	if dp[n][ma * i][mb * i] != 9999:
		a = min(a, dp[n][ma * i][mb * i])
print(-1 if a == 9999 else a)


(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())
table = dict()
table[0, 0] = 0
for (a, b, c) in zip(A, B, C):
	updates = []
	for (e, v) in table.items():
		ne = (e[0] + a, e[1] + b)
		if ne not in table or table[ne] > table[e] + c:
			updates.append((ne, table[e] + c))
	table.update(updates)
max_iter = min(sum(A) // Ma, sum(B) // Mb) + 1
try:
	print(min((table[Ma * i, Mb * i] for i in range(1, max_iter) if (Ma * i, Mb * i) in table)))
except (ValueError, KeyError):
	print(-1)


(n, ma, mb) = map(int, input().split())
U = 400
dp = [[[float('inf')] * (U + 1) for _ in range(U + 1)] for i in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for j in range(U + 1):
		for k in range(U + 1):
			if j < a or k < b:
				dp[i + 1][j][k] = dp[i][j][k]
			else:
				dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - a][k - b] + c)
ans = float('inf')
for i in range(1, 1 + U // max(ma, mb)):
	(na, nb) = (i * ma, i * mb)
	ans = min(ans, dp[-1][na][nb])
if ans == float('inf'):
	print(-1)
else:
	print(ans)


(N, M, K) = map(int, input().split())
table = []
for i in range(N):
	(a, b, c) = map(int, input().split())
	table.append([a, b, c])
inf = 10 ** 9
dp = [[[inf] * 401 for i in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(1, N + 1):
	(a, b, c) = table[i - 1]
	for j in range(401):
		for k in range(401):
			dp[i][j][k] = dp[i - 1][j][k]
			if 400 >= j - a >= 0 and 400 >= k - b >= 0:
				dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + c)
ans = 10 ** 9
i = 1
while max(M, K) * i < 401:
	ans = min(ans, dp[N][M * i][K * i])
	i = i + 1
if ans == 10 ** 9:
	print(-1)
else:
	print(ans)


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


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)


import sys
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
(N, Ma, Mb) = map(int, input().split())
X = [map(int, line.split()) for line in readlines()]
X = [(a * Mb - b * Ma, c) for (a, b, c) in X]
INF = 1 << 30
MAX = 10000
MID = MAX // 2
dp = [INF] * (MAX + 1)
ans = INF
for (i, (x, c)) in enumerate(X):
	if x == 0:
		ans = min(ans, c)
		continue
	if x > 0:
		for j in range(MAX, x - 1, -1):
			dp[j] = min(dp[j], dp[j - x] + c)
	else:
		for j in range(MAX + x):
			dp[j] = min(dp[j], dp[j - x] + c)
	dp[MID + x] = min(dp[MID + x], c)
ans = min(ans, dp[MID])
print(ans if ans < INF else -1)


(n, ma, mb) = map(int, input().split())
dp = [[[5000] * 401 for _ in range(401)] for _ in range(n + 1)]
dp[0][0][0] = 0
maa = mab = 0
for i in range(1, n + 1):
	(a, b, c) = map(int, input().split())
	maa += a
	mab += b
	for j in range(401):
		for k in range(401):
			dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + c)
ans = 5000
for i in range(1, min(maa // ma, mab // mb) + 1):
	if dp[n][ma * i][mb * i] != 5000:
		ans = min(ans, dp[n][ma * i][mb * i])
print(-1 if ans == 5000 else 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])


(N, Ma, Mb) = map(int, input().split())
P = [list(map(int, input().split())) for k in range(N)]
INF = 10000
dp = [[[INF for m in range(401)] for k in range(401)] for l in range(N + 1)]
dp[0][0][0] = 0
for k in range(N):
	a = P[k][0]
	b = P[k][1]
	c = P[k][2]
	for l in range(401):
		for m in range(401):
			if dp[k][l][m] != INF:
				dp[k + 1][l][m] = min(dp[k + 1][l][m], dp[k][l][m])
				dp[k + 1][l + a][m + b] = min(dp[k + 1][l + a][m + b], dp[k][l][m] + c)
ans = INF
for l in range(1, 401):
	for m in range(1, 401):
		if Ma * m == Mb * l:
			ans = min(ans, dp[N][l][m])
print(ans if ans != INF else -1)


(n, Ma, Mb) = map(int, input().split())
inf = float('inf')
dp = [[[inf] * 401 for _ in range(401)] for _ in range(n + 1)]
dp[0][0][0] = 0
l = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(1, n + 1):
	for j in range(401):
		for k in range(401):
			(a, b, c) = l[i - 1]
			dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])
			if j - a >= 0 and k - b >= 0:
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - a][k - b] + c)
ans = 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])
print(ans if ans != inf else -1)


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


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


(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(n)]
inf = float('inf')
dp = [[inf for i in range(n * 10)] for i in range(n * 10)]
for i in range(n):
	for j in range(i * 10 - 1, -1, -1):
		for k in range(i * 10 - 1, -1, -1):
			if dp[j][k] != inf:
				dp[j + abc[i][0]][k + abc[i][1]] = min(dp[j + abc[i][0]][k + abc[i][1]], dp[j][k] + abc[i][2])
	dp[abc[i][0] - 1][abc[i][1] - 1] = min(dp[abc[i][0] - 1][abc[i][1] - 1], abc[i][2])
ans = inf
for j in range(n * 10):
	for k in range(n * 10):
		if ma * (k + 1) == mb * (j + 1):
			ans = min(ans, dp[j][k])
print(ans if ans != inf else -1)


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
stdin = sys.stdin

def na():
	return map(int, stdin.readline().split())
(n, ma, mb) = na()
abcs = []
for i in range(n):
	abcs.append(list(na()))
I = 9999999999
dp = [[I] * 420 for _ in range(420)]
dp[0][0] = 0
sa = 1
sb = 1
for abc in abcs:
	for i in range(sa - 1, -1, -1):
		for j in range(sb - 1, -1, -1):
			dp[i + abc[0]][j + abc[1]] = min(dp[i + abc[0]][j + abc[1]], dp[i][j] + abc[2])
	sa += abc[0]
	sb += abc[1]
x = ma
y = mb
ret = I
while x < 420 and y < 420:
	ret = min(ret, dp[x][y])
	x += ma
	y += mb
if ret == I:
	print(-1)
else:
	print(ret)


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


(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) = map(int, input().split())
INF = 10 ** 17
dp = [[[INF] * (10 * n + 1) for i in range(10 * n + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
ans = 10 ** 17
for i in range(n):
	(a, b, c) = map(int, input().split())
	for j in range(10 * n + 1):
		for k in range(10 * n + 1):
			if dp[i][j][k] != INF:
				dp[i + 1][j + a][k + b] = min(dp[i + 1][j + a][k + b], dp[i][j][k] + c)
			dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
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])
if ans == INF:
	print(-1)
else:
	print(ans)


(n, ma, mb) = 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(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)


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())
dp = [{} for i in range(N + 1)]
dp[0][0, 0] = 0
for i in range(N):
	(a, b, c) = 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)
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)


(N, *M) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in [0] * N]
INF = 100 * 40 * 100
dp = [[[INF] * 500 for _ in [0] * 500] for _ in [0] * (N + 1)]
dp[0][0][0] = 0
for i in range(1, N + 1):
	(a, b, c) = abc[i - 1]
	for j in range(410):
		for k in range(410):
			dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + c)
ans = min([dp[-1][M[0] * i][M[1] * i] for i in range(1, 1 + 400 // max(M))])
if ans == INF:
	ans = -1
print(ans)


import sys
input = sys.stdin.readline
(N, a, b) = map(int, input().split())
t = []
dp = [[[float('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):
	(x, y, c) = map(int, input().split())
	for j in range(N * 10 + 1):
		for k in range(N * 10 + 1):
			if dp[i][j][k] != float('inf'):
				dp[i + 1][j + x][k + y] = min(dp[i + 1][j + x][k + y], dp[i][j][k] + c)
			dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
res = float('inf')
for j in range(1, N * 10 + 1):
	for k in range(1, N * 10 + 1):
		if j / a == k / b:
			res = min(res, dp[-1][j][k])
if res != float('inf'):
	print(res)
else:
	print(-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)
						exit()
					temp_list.append((a + pre_a, b + pre_b, pre_i + [i]))
	dp.append(temp_list)
print('-1')


(N, Ma, Mb) = map(int, input().split())
G = []
for i in range(N):
	(a, b, c) = map(int, input().split())
	G.append((a, b, c))
M = 1 + max(sum([a for (a, b, c) in G]), sum([b for (a, b, c) in G]))
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for (a, b, c) in G:
	for i in reversed(range(0, M - a)):
		for j in reversed(range(0, M - b)):
			dp[(i + a) * M + (j + b)] = min(dp[(i + a) * M + (j + b)], dp[i * M + j] + c)
ans = INF
x = 1
while Ma * x < M and Mb * x < M:
	ans = min(ans, dp[Ma * x * M + Mb * x])
	x += 1
if ans >= INF:
	ans = -1
print(ans)


import sys
inf = float('inf')
(n, ma, mb) = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
for _ in range(n):
	(a, b, c) = map(int, input().split())
	for aa in range(400, 0, -1):
		for bb in range(400, 0, -1):
			if t[aa][bb] == inf:
				continue
			if t[a + aa][b + bb] > c + t[aa][bb]:
				t[a + aa][b + bb] = c + t[aa][bb]
	if t[a][b] > c:
		t[a][b] = 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:
	print(-1)
else:
	print(result)


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


(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) = map(int, input().split())
INF = 10 ** 10
dp = [[[INF for _ in range(400 + 5)] for _ in range(400 + 5)] for _ in range(n + 5)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for ta in range(400 + 5 - a):
		for tb in range(400 + 5 - b):
			dp[i + 1][ta][tb] = min(dp[i + 1][ta][tb], dp[i][ta][tb])
			dp[i + 1][ta + a][tb + b] = min(dp[i + 1][ta + a][tb + b], dp[i][ta][tb] + c)
ans = INF
for i in range(1, n + 1):
	t = 1
	while max(ma, mb) * t <= 400:
		ans = min(ans, dp[i][ma * t][mb * t])
		t += 1
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, 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 collections
import copy
INF = 10000
(N, Ma, Mb) = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]
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)


INF = 10 ** 10
(n, ma, mb) = [int(item) for item in input().split()]
abc = [[int(item) for item in 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)


from fractions import gcd

def readln():
	_res = list(map(int, str(input()).split(' ')))
	return _res

def push(k, v):
	if k in f:
		f[k] = min(f[k], v)
	else:
		f[k] = v

def add(k, v):
	es = []
	for e in f:
		es.append([e, f[e]])
	for ee in es:
		push(ee[0] + k, ee[1] + v)
	push(k, v)
a = readln()
(n, x, y) = (a[0], a[1], a[2])
f = {}
for i in range(0, n):
	a = readln()
	add(a[0] * y - a[1] * x, a[2])
if 0 in f:
	print(f[0])
else:
	print('-1')


inf = float('inf')
(N, Ma, Mb) = 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) = map(int, input().split())
	max_a += a
	max_b += b
	for j in reversed(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)


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)


def main():
	INF = 10 ** 5
	(n, ma, mb) = map(int, input().split())
	dp = [[INF] * 401 for _ in range(401)]
	dp[0][0] = 0
	for _ in range(n):
		(a, b, c) = map(int, input().split())
		for i in range(400 - a, -1, -1):
			dpi = dp[i]
			dpia = dp[i + a]
			for j in range(400 - b, -1, -1):
				if dpia[j + b] > dpi[j] + c:
					dpia[j + b] = dpi[j] + c
	ans = INF
	for i in range(1, 400):
		if ma * i > 400 or mb * i > 400:
			break
		ans = min(ans, dp[ma * i][mb * i])
	if ans >= INF:
		print(-1)
	else:
		print(ans)
main()


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())
abc = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
dp = [[[INF] * 500 for i in range(500)] for x in range(n + 1)]
dp[0][0][0] = 0
for (k, (a, b, c)) in enumerate(abc):
	for i in range(400):
		for j in range(400):
			dp[k + 1][i][j] = min(dp[k + 1][i][j], dp[k][i][j])
			dp[k + 1][i + a][j + b] = min(dp[k][i + a][j + b], dp[k][i][j] + c)
ans = INF
for i in range(1, 500):
	(Ma, Mb) = (i * ma, i * mb)
	if Ma > 400 or Mb > 400:
		break
	ans = min(ans, dp[n][Ma][Mb])
if ans == INF:
	print(-1)
else:
	print(ans)


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


import sys
input = sys.stdin.readline
(n, ma, mb) = map(int, input().split())
inf = 10000
med = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[[inf] * 401 for _ in range(401)] for _ in range(n + 1)]
dp[0][0][0] = 0
for k in range(n):
	for i in range(401):
		for j in range(401):
			(a, b, c) = med[k]
			if i - a >= 0 and j - b >= 0:
				dp[k + 1][i][j] = min(dp[k][i][j], dp[k][i - a][j - b] + c)
			else:
				dp[k + 1][i][j] = dp[k][i][j]
ans = inf
for k in range(1, 401):
	if k * ma > 400 or k * mb > 400:
		break
	(x, y) = (k * ma, k * mb)
	ans = min(ans, dp[n][x][y])
print(-1 if ans == inf else 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)


import fractions, copy, collections
(n, ma, mb) = map(int, input().split())
rows = [map(int, input().split()) for _ in range(n)]
ht = {(0, 0): 0}
for (a, b, c) in rows:
	temp = copy.deepcopy(ht)
	for (x, y) in ht:
		if not (x + a, y + b) in ht or ht[x, y] + c < ht[x + a, y + b]:
			temp[x + a, y + b] = ht[x, y] + c
	ht = temp
ans = float('inf')
for (a, b) in ht:
	if b != 0 and fractions.Fraction(ma, mb) == fractions.Fraction(a, b):
		ans = min(ans, ht[a, b])
print(-1 if ans == float('inf') else ans)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from itertools import product
from copy import deepcopy

def resolve():
	(n, ma, mb) = map(int, input().split())
	ABC = [tuple(map(int, input().split())) for _ in range(n)]
	M = 400
	dp = [[INF] * (M + 1) for _ in range(M + 1)]
	dp[0][0] = 0
	for (a, b, c) in ABC:
		for (x, y) in product(range(M, -1, -1), repeat=2):
			if x + a <= M and y + b <= M:
				dp[x + a][y + b] = min(dp[x + a][y + b], dp[x][y] + c)
	ans = INF
	for (x, y) in product(range(1, M + 1), repeat=2):
		if x * mb == y * ma:
			ans = min(ans, dp[x][y])
	if ans == INF:
		ans = -1
	print(ans)
resolve()


INF = 10 ** 18
(N, Ma, Mb) = map(int, input().split())
dp = [[[INF for k in range(401)] for j in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for j in range(400):
		for k in range(400):
			dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
			if j + a <= 400 and k + b <= 400:
				dp[i + 1][j + a][k + b] = min(dp[i + 1][j + a][k + b], dp[i][j][k] + c)
res = INF
for j in range(1, 401):
	for k in range(1, 401):
		if k * Ma == j * Mb:
			res = min(res, dp[N][j][k])
print(res if res != INF else -1)


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
	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))
	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
		elif 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
	(ans, pre) = allptn(abc[:n // 2], ma, mb)
	(ret, pos) = allptn(abc[n // 2:], ma, mb)
	ans = min(ans, ret)
	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()


(N, Ma, Mb) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(N)]
inf = 10 ** 9
dp = [[inf for i in range(N * 10 + 1)] for i in range(N * 10 + 1)]
dp[0][0] = 0
max_a = 0
max_b = 0
for i in range(N):
	max_a += abc[i][0]
	max_b += abc[i][1]
	for ai in range(abc[i][0], max_a + 1)[::-1]:
		for bi in range(abc[i][1], max_b + 1)[::-1]:
			dp[ai][bi] = min(dp[ai][bi], dp[ai - abc[i][0]][bi - abc[i][1]] + abc[i][2])
ans = inf
for i in range(1, min(max_a // Ma, max_b // Mb)):
	ans = min(ans, dp[i * Ma][i * Mb])
if ans == inf:
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [[[5000] * 401 for _ in range(401)] for _ in range(41)]
dp[0][0][0] = 0
for i in range(N):
	(a, b, c) = arr[i]
	for j in range(10 * N + 1):
		for k in range(10 * N + 1):
			if dp[i][j][k] == 5000:
				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 = 5000
for i in range(1, 401):
	if i * Ma > 400 or i * Mb > 400:
		break
	ans = min(ans, dp[N][i * Ma][i * Mb])
if ans == 5000:
	print(-1)
else:
	print(ans)


(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(n)]
dp = [[[10 ** 9] * 401 for i in range(401)] for j in range(n + 1)]
dp[0][0][0] = 0
for i in range(1, n + 1):
	for j in range(401):
		for k in range(401):
			if j - abc[i - 1][0] >= 0 and k - abc[i - 1][1] >= 0:
				dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - abc[i - 1][0]][k - abc[i - 1][1]] + abc[i - 1][2])
			else:
				dp[i][j][k] = dp[i - 1][j][k]
ans = 10 ** 18
for j in range(1, 401):
	for k in range(1, 401):
		if dp[n][j][k] < 10 ** 9 and k * ma == j * mb:
			ans = min(ans, dp[n][j][k])
if ans == 10 ** 18:
	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)


from collections import defaultdict
(N, Ma, Mb) = map(int, input().split())
dp = [defaultdict(lambda : float('inf')) for _ in range(2)]
zero = float('inf')
dp[0][0] = dp[1][0] = 0
for _ in range(N):
	(a, b, c) = map(int, input().split())
	d = a * Mb - b * Ma
	if d == 0:
		zero = min(zero, c)
	else:
		i = 0 if d > 0 else 1
		d = abs(d)
		item = list(dp[i].items())[::-1]
		for (k, v) in item:
			dp[i][k + d] = min(dp[i][k + d], dp[i][k] + c)
ret = zero
for (k, v) in dp[0].items():
	if k in dp[1] and k != 0:
		ret = min(ret, v + dp[1][k])
if ret == float('inf'):
	print(-1)
else:
	print(ret)


(N, Ma, Mb) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dp = [[[inf] * 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 j - abc[i][0] >= 0 and k - abc[i][1] >= 0:
				dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - abc[i][0]][k - abc[i][1]] + abc[i][2])
			else:
				dp[i + 1][j][k] = dp[i][j][k]
ans = inf
for a in range(1, 401):
	if a % Ma == 0:
		b = a // Ma * Mb
		if b <= 401:
			ans = min(ans, dp[N][a][b])
if ans == inf:
	ans = -1
print(ans)


(n, ma, mb) = map(int, input().split())
dp = [[[float('inf') for _ in range(401)] for _ in range(401)] for _ in range(n)]
dp[0][0][0] = 0
(a0, b0, c0) = map(int, input().split())
dp[0][a0][b0] = c0
for i in range(1, n):
	dp[i][0][0] = 0
	(a, b, c) = map(int, input().split())
	for j in range(401):
		for k in range(401):
			if j >= a and k >= b:
				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')
cnt = 400 // max(ma, mb)
for i in range(1, cnt + 1):
	ans = min(ans, dp[-1][ma * i][mb * i])
if ans <= 4000:
	print(ans)
else:
	print(-1)


inf = float('inf')
(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 = [[inf] * 420 for _ in range(420)]
dp[0][0] = 0
for (a, b, c) in ABC:
	for i in range(410, -1, -1):
		for j in range(410, -1, -1):
			if dp[i][j] < inf:
				dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)
ans = inf
n = 1
while max(Ma * n, Mb * n) < 420:
	ans = min(ans, dp[Ma * n][Mb * n])
	n += 1
print(ans if ans < inf else -1)


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


(N, Ma, Mb) = list(map(int, input().strip().split()))
abc = [list(map(int, input().strip().split())) for i in range(N)]
maxW = N * 10
dp = [{} for __ in range(N + 1)]
dp[0][0, 0] = 0
for i in range(N):
	(a, b, c) = abc[i]
	for (k, v) in dp[i].items():
		dp[i + 1][k] = min(dp[i][k], dp[i + 1][k] if k in dp[i + 1] else float('inf'))
		dp[i + 1][k[0] + a, k[1] + b] = min(dp[i][k] + c, dp[i + 1][k[0] + a, k[1] + b] if (k[0] + a, k[1] + b) in dp[i + 1] else float('inf'))
cost = float('inf')
Mad = Ma
Mbd = Mb
while Ma <= maxW and Mb <= maxW:
	if (Ma, Mb) in dp[-1]:
		cost = min(dp[-1][Ma, Mb], cost)
	Ma += Mad
	Mb += Mbd
print(-1 if cost == float('inf') else cost)


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, A, B) = list(map(int, input().split()))
item = []
for i in range(N):
	(a, b, c) = list(map(int, input().split()))
	item.append([a, b, c])
D = [[[10 ** 27 for i in range(401)] for j in range(401)] for k in range(N + 1)]
D[0][0][0] = 0
for i in range(N):
	for j in range(401):
		for k in range(401):
			if D[i][j][k] < 10 ** 26:
				D[i + 1][j][k] = min(D[i + 1][j][k], D[i][j][k])
				D[i + 1][j + item[i][0]][k + item[i][1]] = min(D[i + 1][j + item[i][0]][k + item[i][1]], D[i][j][k] + item[i][2])
i = 1
min_cost = 10 ** 27
while A * i <= 400 and B * i <= 400:
	min_cost = min(D[N][A * i][B * i], min_cost)
	i += 1
if min_cost == 10 ** 27:
	print(-1)
else:
	print(min_cost)


(n, ma, mb) = list(map(int, input().split()))
G = []
for i in range(n):
	G.append(list(map(int, input().split())))
DP = [[10000 for _ in range(500)] for _ in range(500)]
DP[0][0] = 0
for i in range(n):
	for j in reversed(range(400)):
		for k in reversed(range(400)):
			if DP[j][k] == 10000:
				continue
			DP[j + G[i][0]][k + G[i][1]] = min(DP[j][k] + G[i][2], DP[j + G[i][0]][k + G[i][1]])
ans = 10000
for i in range(1, min(400 // ma, 400 // mb) + 1):
	ans = min(ans, DP[ma * i][mb * i])
if ans == 10000:
	print(-1)
else:
	print(ans)


(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 copy
(N, Ma, Mb) = [int(n) for n in input().split()]
pd = {(0, 0): 0}
for i in range(N):
	(a, b, c) = [int(n) for n in input().split()]
	pdcopy = copy.deepcopy(pd)
	for (k, v) in pdcopy.items():
		nk = (k[0] + a, k[1] + b)
		if nk in pd:
			if pd[nk] > v + c:
				pd[nk] = v + c
		else:
			pd[nk] = v + c
mp = 1000000
for i in range(1, 401):
	if (Ma * i, Mb * i) in pd:
		mp = min(pd[Ma * i, Mb * i], mp)
if mp == 1000000:
	print(-1)
else:
	print(mp)


import sys
read = sys.stdin.readline
(N, Ma, Mb) = 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)


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


INF = float('inf')
(N, Ma, Mb) = map(int, input().split())
abc = []
dp = [[INF] * 401 for i in range(401)]
dp[0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for A in reversed(range(401)):
		for B in reversed(range(401)):
			if B - b >= 0 and A - a >= 0:
				dp[A][B] = min(dp[A][B], dp[A - a][B - b] + c)
ans = INF
for i in range(1, 401):
	if i * Ma > 400 or i * Mb > 400:
		break
	ans = min(ans, dp[Ma * i][Mb * i])
print(ans if ans != INF else -1)


(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, M, L) = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
INF = 10 ** 9
DP = [[INF] * 411 for i in range(411)]
DP[0][0] = 0
for i in range(N):
	for j in range(400, -1, -1):
		for k in range(401):
			DP[j + X[i][0]][k + X[i][1]] = min(DP[j + X[i][0]][k + X[i][1]], DP[j][k] + X[i][2])
P = INF
for i in range(1, 401):
	if i * max(M, L) > 400:
		break
	P = min(P, DP[i * M][i * L])
if P == INF:
	print(-1)
else:
	print(P)


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


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


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


I = lambda : list(map(int, input().split()))
(n, Ma, Mb) = I()
m = [[0, 0, 0]] + [I() for _ in range(n)]
dp = [[[10 ** 18] * (10 * n + 1) for _ in range(10 * n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(1, n + 1):
	for j in range(10 * n + 1):
		if j - m[i][0] < 0:
			dp[i][j] = dp[i - 1][j]
			continue
		for k in range(10 * n + 1):
			if k - m[i][1] < 0:
				dp[i][j][k] = dp[i - 1][j][k]
			else:
				dp[i][j][k] = min(dp[i - 1][j - m[i][0]][k - m[i][1]] + m[i][2], dp[i - 1][j][k])
ans = 10 ** 18
for i in range(1, 10 * n + 1):
	j = Mb * i / Ma
	if j == int(j) and j < 10 * n + 2:
		ans = min(ans, dp[-1][i][int(j)])
print(-(ans == 10 ** 18) or ans)


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


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


(n, ma, mb) = map(int, input().split())
x = []
amax = 0
bmax = 0
for i in range(n):
	(x1, y1, z1) = [int(i) for i in input().split()]
	x.append([x1, y1, z1])
	amax += x1
	bmax += y1
inf = float('inf')
dp = [[inf] * (amax + 1) for i in range(bmax + 1)]
dp[0][0] = 0
aru = {(0, 0)}
for i in x:
	a = i[0]
	b = i[1]
	c = i[2]
	aru2 = list(aru)
	aru2 = sorted(aru2, key=lambda x: -x[0])
	for j in aru2:
		dp[j[1] + b][j[0] + a] = min(dp[j[1] + b][j[0] + a], dp[j[1]][j[0]] + c)
		aru.add((j[0] + a, j[1] + b))
ans = inf
mam = ma + 0
mbm = mb + 0
while amax >= ma and bmax >= mb:
	suu = dp[mb][ma]
	ans = min(ans, suu)
	mb += mbm
	ma += mam
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))
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)


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 sys
input = sys.stdin.readline
(N, Ma, Mb) = map(int, input().split())
MAX = 400
INF = float('inf')
dp = [[INF] * (MAX + 1) for _ in range(MAX + 1)]
dp[0][0] = 0
for _ in range(N):
	(a, b, c) = map(int, input().split())
	for i in range(a, MAX + 1)[::-1]:
		for j in range(b, MAX + 1)[::-1]:
			dp[i][j] = min(dp[i][j], dp[i - a][j - b] + c)
ans = INF
x = 1
while Ma * x <= MAX and Mb * x <= MAX:
	ans = min(ans, dp[Ma * x][Mb * x])
	x += 1
print(ans if ans < INF else -1)


INFTY = 10 ** 4
(N, Ma, Mb) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [[[INFTY 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):
	for j in range(401):
		for k in range(401):
			dp[i][j][k] = dp[i - 1][j][k]
			a = A[i - 1][0]
			b = A[i - 1][1]
			c = A[i - 1][2]
			if j >= a and k >= b:
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - a][k - b] + c)
cmin = INFTY
for j in range(1, 401):
	for k in range(1, 401):
		if j * Mb == k * Ma:
			cmin = min(cmin, dp[N][j][k])
if cmin >= INFTY:
	print(-1)
else:
	print(cmin)


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


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)


(N, Ma, Mb) = map(int, input().split())
sz = 401
table = [[99999999] * (sz + 1) for _ in range(sz + 1)]
table[0][0] = 0
for n in range(N):
	(a, b, c) = map(int, input().split())
	for i in range(sz, -1, -1):
		for j in range(sz, -1, -1):
			if table[i][j] != 99999999:
				table[i + a][j + b] = min(table[i + a][j + b], table[i][j] + c)
ans = 99999999
(i, j) = (Ma, Mb)
while i <= sz and j <= sz:
	ans = min(ans, table[i][j])
	i += Ma
	j += Mb
print(ans if ans != 99999999 else -1)


(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) = map(int, input().split())
medic = [tuple(map(int, input().split())) for i in range(N)]
from collections import defaultdict
dp = defaultdict(lambda : float('inf'))
dp[0, 0] = 0
for (a, b, c) in medic:
	dpc = dp.copy()
	for (k, v) in dpc.items():
		(x, y) = k
		dp[x + a, y + b] = min(dp[x + a, y + b], v + c)
ans = 10 ** 10
for i in range(1, 1 + N):
	ans = min(ans, dp[Ma * i, Mb * i])
if ans > 10 ** 9:
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = [int(_) for _ in input().split()]
T = [[int(_) for _ in input().split()] for i in range(N)]
dp = [[float('inf') for i in range(401)] for i in range(401)]
dp[0][0] = 0
sum_a = 0
sum_b = 0
for x in range(N):
	(a, b, c) = T[x]
	sum_a += a
	sum_b += b
	for i in list(range(a, sum_a + 1))[::-1]:
		for j in list(range(b, sum_b + 1))[::-1]:
			dp[i][j] = min(dp[i][j], dp[i - a][j - b] + c)
ans = float('inf')
for i in range(1, sum_a + 1):
	for j in range(1, sum_b + 1):
		if i * Mb == j * Ma:
			ans = min(ans, dp[i][j])
print(ans if ans != float('inf') else -1)


import sys
input = sys.stdin.readline
(n, ma, mb) = map(int, input().split())
dp = [[[float('inf')] * 500 for _ in range(500)] for i in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for j in range(450):
		for k in range(450):
			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 = float('inf')
i = 1
while i * ma < 450 and i * mb < 450:
	ans = min(ans, dp[-1][ma * i][mb * i])
	i += 1
print(ans if ans != float('inf') else -1)


(N, Ma, Mb) = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in [0] * N]
INFTY = 10 ** 8
dp = [[[INFTY] * 10 * (N + 1) for _ in [0] * 10 * (N + 1)] for _ in [0] * (N + 1)]
dp[0][0][0] = 0
for i in range(1, N + 1):
	(a, b, c) = ABC[i - 1]
	for j in range(10 * (N + 1)):
		for k in range(10 * (N + 1)):
			dp[i][j][k] = dp[i - 1][j][k]
			if j - a >= 0 and k - b >= 0:
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - a][k - b] + c)
ans = min((dp[-1][Ma * k][Mb * k] for k in range(1, (10 * (N + 1) - 1) // max(Ma, Mb) + 1)))
if ans == INFTY:
	ans = -1
print(ans)


from itertools import permutations
(n, ma, mb) = map(int, input().split())
abc = []
inf = float('INF')
hw = 400 + 1
dp = [[inf for i in range(hw)] for j in range(hw)]
dp[0][0] = 0
for _ in range(n):
	(a, b, c) = map(int, input().split())
	abc.append((a, b, c))
abc.sort(key=lambda x: (-x[0], x[1]))
for (a, b, c) in abc:
	for i in range(hw - a)[::-1]:
		for j in range(hw - b)[::-1]:
			if dp[i + a][j + b] > dp[i][j] + c:
				dp[i + a][j + b] = dp[i][j] + c
(a, b) = (ma, mb)
ans = [dp[a * i][b * i] for i in range(1, hw // max(a, b)) if dp[a * i][b * i] < inf]
print(min(ans) if len(ans) else -1)


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


(n, Ma, Mb) = map(int, input().split())
dp = [[[1000000] * 510 for i in range(510)] for j in range(n + 1)]
dp[0][0][0] = 0
for i in range(1, n + 1):
	(a, b, c) = map(int, input().split())
	for j in range(410):
		for k in range(410):
			dp[i][j][k] = min(dp[i - 1][j][k], dp[i][j][k])
			p = j + a
			q = k + b
			dp[i][p][q] = min(dp[i][p][q], dp[i - 1][j][k] + c)
ans = 1000000
for i in range(1, 410 // max(Ma, Mb) + 1):
	ans = min(dp[n][i * Ma][i * Mb], ans)
if ans == 1000000:
	print(-1)
else:
	print(ans)


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) = map(int, input().split())
INF = 10 ** 9
dp = {(0, 0): 0}
for _ in range(n):
	(a, b, c) = map(int, input().split())
	for ((ea, eb), ec) in dp.copy().items():
		dp[ea + a, eb + b] = min(dp.get((ea + a, eb + b), INF), ec + c)
ans = min((dp.get((i * ma, i * mb), INF) for i in range(1, 401)))
print(ans if ans != INF else -1)


from collections import defaultdict
(n, ma, mb) = map(int, input().split())
dp = defaultdict(lambda : float('inf'))
dp[0, 0] = 0
sa = 0
for _ in range(n):
	(a, b, c) = map(int, input().split())
	for ((i, j), d) in dp.copy().items():
		k = (i + a, j + b)
		dp[k] = min(dp[k], d + c)
	sa += a
ans = float('inf')
i = 1
while ma * i <= sa:
	ta = ma * i
	tb = mb * i
	i += 1
	ans = min(ans, dp[ta, tb])
print(-1 if ans == float('inf') else ans)


(N, Ma, Mb) = map(int, input().split())
medic = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict
inf = float('inf')
dp = defaultdict(lambda : inf)
dp[0, 0] = 0
for n in range(N):
	dpc = dp.copy()
	(a, b, c) = medic[n]
	for (d, cost) in dpc.items():
		(da, db) = d
		dp[da + a, db + b] = min(dp[da + a, db + b], c + cost)
ans = inf
(nowa, nowb) = (Ma, Mb)
while nowa <= 400 and nowb <= 400:
	ans = min(ans, dp[nowa, nowb])
	nowa += Ma
	nowb += Mb
if ans > 4000:
	ans = -1
print(ans)


import sys
input = sys.stdin.readline

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


ab = [[float('inf') for j in range(401)] for i in range(401)]
(n, ma, mb) = map(int, input().split())
(a, b, c) = map(int, input().split())
ab[a][b] = c
ab[0][0] = 0
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	for j in range(400, -1, -1):
		for k in range(400, -1, -1):
			if ab[j][k] != float('inf'):
				ab[j + a][k + b] = min(ab[j][k] + c, ab[j + a][k + b])
ans = float('inf')
(a, b) = (ma, mb)
while a < 401 and b < 401:
	ans = min(ans, ab[a][b])
	a += ma
	b += mb
if ans == float('inf'):
	ans = -1
print(ans)


import sys
input = sys.stdin.buffer.readline
(N, Ma, Mb) = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 15
dp = [[INF for j in range(401)] for i 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)
answer = INF
for i in range(1, 401):
	for j in range(1, 401):
		if dp[i][j] != INF and i / j == Ma / Mb:
			answer = min(answer, dp[i][j])
print(answer if answer != INF else -1)


INF = float('inf')
MAXAB = 10
(n, ma, mb) = 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) = 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)


(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) = map(int, input().split())
src = [tuple(map(int, input().split())) for i in range(N)]
INF = 10 ** 9
dp = [[INF for j in range(401)] for i in range(401)]
dp[0][0] = 0
maxa = maxb = 0
for (a, b, c) in src:
	for ai in range(maxa, -1, -1):
		for bi in range(maxb, -1, -1):
			dp[ai + a][bi + b] = min(dp[ai + a][bi + b], dp[ai][bi] + c)
	maxa += a
	maxb += b
ans = INF
for i in range(1, 401):
	if MA * i > 400 or MB * i > 400:
		break
	ans = min(ans, dp[MA * i][MB * i])
print(-1 if ans == INF else 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])


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


def inpl():
	return map(int, input().split())
(N, Ma, Mb) = inpl()
INF = 4001
DP = [[INF] * 411 for _ in range(411)]
DP[0][0] = 0
for n in range(N):
	DP2 = [[INF] * 411 for _ in range(411)]
	(a, b, c) = inpl()
	for i in range(10 * (n + 1) + 1):
		for j in range(10 * (n + 1) + 1):
			if DP[i][j] == INF:
				continue
			DP2[i][j] = min(DP[i][j], DP2[i][j])
			DP2[i + a][j + b] = min(DP[i + a][j + b], DP[i][j] + c)
	DP = DP2
x = 1
ans = INF
while Ma * x <= 400 and Mb * x <= 400:
	ans = min(ans, DP[Ma * x][Mb * x])
	x += 1
if ans < INF:
	print(ans)
else:
	print(-1)


(N, Ma, Mb) = map(int, input().split())
(a, b, c) = map(list, zip(*[list(map(int, input().split())) for i in range(N)]))
(ma, mb) = (sum(a), sum(b))
MAX = 5000
dp = [[[MAX] * (mb + 1) for i in range(ma + 1)] for j in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	for j in range(ma):
		for k in range(mb):
			dp[i + 1][j][k] = min(dp[i][j][k], dp[i + 1][j][k])
			if j + a[i] <= ma and k + b[i] <= mb:
				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 = MAX
x = 1
while x * Ma <= ma and x * Mb <= mb:
	ans = min(ans, dp[N][x * Ma][x * Mb])
	x += 1
print(ans if ans < MAX else -1)


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


INF = 10 ** 5
(N, Ma, Mb) = map(int, input().split())
dp = [[[INF for i in range(10 * N + 1)] for j in range(10 * N + 1)] for k in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for j in range(10 * N + 1):
		for k in range(10 * N + 1):
			dp[i + 1][j][k] = min(dp[i][j][k], dp[i + 1][j][k])
			if j + a <= 10 * N and k + b <= 10 * N:
				dp[i + 1][j + a][k + b] = min(dp[i][j][k] + c, dp[i + 1][j + a][k + b])
ans = INF
i = 1
while Ma * i <= 10 * N and Mb * i <= 10 * N:
	ans = min(ans, dp[N][Ma * i][Mb * i])
	i += 1
if ans == INF:
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = list(map(int, input().split()))
mix = set([(0, 0)])
ans = 10 ** 9
cost = {(0, 0): 0}
for i in range(N):
	(a, b, c) = list(map(int, input().split()))
	tmp = mix.copy()
	tmp2 = cost.copy()
	for x in tmp:
		d = x[0] + a
		e = x[1] + b
		f = min(tmp2.get((d, e), 10 ** 9), tmp2[x] + c)
		cost[d, e] = f
		mix.add((d, e))
		if d * Mb == e * Ma and f < ans:
			ans = f
if ans == 10 ** 9:
	ans = -1
print(ans)


(N, Ma, Mb) = map(int, input().split())
abc = []
INF = float('inf')
for i in range(N):
	(a, b, c) = map(int, input().split())
	abc.append((a, b, c))
stack = set([(0, 0)])
dp = [[[INF] * 401 for j in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	dp[i + 1][0][0] = 0
	(a, b, c) = abc[i]
	stack_ = set()
	for (x, y) in stack:
		dp[i + 1][x][y] = min(dp[i][x][y], dp[i + 1][x][y])
		dp[i + 1][x + a][y + b] = min(dp[i + 1][x + a][y + b], dp[i][x + a][y + b], dp[i][x][y] + c)
		stack_.add((x + a, y + b))
		stack_.add((x, y))
	stack = stack_
k = 1
ans = INF
while Ma * k <= 400 and Mb * k <= 400:
	ans = min(dp[N][Ma * k][Mb * k], ans)
	k += 1
if ans == INF:
	print(-1)
else:
	print(ans)


import sys
input = sys.stdin.readline
(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [5000 for i in range(170000)]
dp[0] = 0
for (a, b, c) in abc:
	dpn = dp[:]
	for i in range(170000):
		nex = 401 * b + a + i
		if nex >= 170000:
			break
		dpn[nex] = min(dpn[nex], dp[i] + c)
	dp = dpn
ans = 50000
for i in range(1, 170000):
	a = i % 401
	b = i // 401
	if ma * b == mb * a:
		ans = min(ans, dp[i])
if ans == 5000:
	print(-1)
else:
	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)


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)


def solve():
	(N, M_a, M_b) = [int(x) for x in input().split()]
	inf = 100000
	t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
	t[0][0] = 0
	for _ in range(N):
		(ai, bi, ci) = [int(x) for x in input().split()]
		for ta in reversed(range(ai, len(t))):
			for tb in reversed(range(bi, len(t[0]))):
				t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
	ans = min((t[k * M_a][k * M_b] for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)))
	print(-1 if ans >= inf else ans)
solve()


import itertools
(N, Ma, Mb) = map(int, input().split())
L = [[int(i) for i in input().split()] for _ in range(N)]
inf = N * 101
dp = [[[inf for _ in range(N * 10 + 11)] for _ in range(N * 10 + 11)] for _ in range(N + 1)]
dp[0][0][0] = 0
cmb = itertools.product(range(N), range(N * 10), range(N * 10))
for (i, j, k) in cmb:
	dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
	dp[i + 1][j + L[i][0]][k + L[i][1]] = min(dp[i + 1][j + L[i][0]][k + L[i][1]], dp[i][j][k] + L[i][2])
ans = inf
for i in range(1, N * 10 // max(Ma, Mb)):
	ans = min(ans, dp[N][i * Ma][i * Mb])
if ans == inf:
	print(-1)
else:
	print(ans)


def inpl():
	return [int(i) for i in input().split()]
(N, Ma, Mb) = inpl()
inf = float('inf')
H = {(0, 0): 0}
for i in range(N):
	(a, b, c) = inpl()
	for ((ia, ib), ic) in H.copy().items():
		H[ia + a, ib + b] = min(H.get((ia + a, ib + b), inf), ic + c)
ans = min((H.get((i * Ma, i * Mb), inf) for i in range(1, 401)))
print(-1 if ans == inf else ans)


(N, Ma, Mb) = map(int, input().split())
INF = 10 ** 9
dp = {(0, 0): 0}
for _ in range(N):
	(a, b, c) = map(int, input().split())
	for ((pa, pb), pc) in dp.copy().items():
		dp[pa + a, pb + b] = min(dp.get((pa + a, pb + b), INF), pc + c)
ans = min((dp.get((i * Ma, i * Mb), INF) for i in range(1, 401)))
print(ans if ans != INF else -1)


(n, ma, mb) = map(int, input().split())
INF = 10 ** 18
dp = [[[INF for _ in range(401)] for _ in range(401)] for _ in range(n + 1)]
ce = [[] for _ in range(n)]
for i in range(n):
	ce[i] = tuple(map(int, input().split()))
dp[0][0][0] = 0
for k in range(n):
	for i in range(401):
		for j in range(401):
			(a, b, c) = ce[k]
			dp[k + 1][i][j] = min(dp[k + 1][i][j], dp[k][i][j])
			if i + a < 401 and j + b < 401:
				dp[k + 1][i + a][j + b] = min(dp[k + 1][i + a][j + b], dp[k][i][j] + c)
ans = 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 == INF:
	ans = -1
print(ans)


(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in [0] * n]
memo = [[10 ** 4 for _ in [0] * (n * 10 + 1)] for _ in [0] * (n * 10 + 1)]
memo[0][0] = 0
for N in range(n):
	for i in range(N * 10, -1, -1):
		for j in range(N * 10, -1, -1):
			(a, b, c) = abc[N]
			memo[i + a][j + b] = min(memo[i + a][j + b], memo[i][j] + c)
m = 10 ** 4
for i in range(1, n * 10):
	for j in range(1, n * 10):
		if i * mb == ma * j:
			m = min(m, memo[i][j])
if m == 10 ** 4:
	print(-1)
else:
	print(m)


(n, ma, mb) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [[[float('INF')] * (n * 10 + 2) for i in range(n * 10 + 2)] for j in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	(a, b, c) = l[i]
	for j in range(n * 10 + 1):
		for k in range(n * 10 + 1):
			if j >= a and k >= b:
				dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - a][k - b] + c)
			elif dp[i][j][k] != float('INF'):
				dp[i + 1][j][k] = dp[i][j][k]
ans = float('INF')
for i in range(1, n * 10 + 1):
	j = i * mb / ma
	if j % 1 == 0 and j < n * 10:
		ans = min(ans, dp[-1][i][int(j)])
if ans == float('INF'):
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = map(int, input().split())
INF = 10 ** 9 + 7
dp = [[[INF] * 401 for _ in range(401)] for __ in range(N + 1)]
dp[0][0][0] = 0
for n in range(N):
	(x, y, c) = map(int, input().split())
	for a in range(401):
		for b in range(401):
			if dp[n][a][b] == INF:
				continue
			dp[n + 1][a][b] = min(dp[n + 1][a][b], dp[n][a][b])
			if a + x <= 400 and b + y <= 400:
				dp[n + 1][a + x][b + y] = min(dp[n + 1][a + x][b + y], dp[n][a][b] + c)
ans = INF
(a, b) = (0, 0)
while True:
	a += Ma
	b += Mb
	if a > 400 or b > 400:
		break
	ans = min(ans, dp[N][a][b])
if ans == INF:
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = map(int, input().split())
dp = [[10 ** 18 for _ in range(401)] for _ in range(401)]
dp[0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for ca in range(i * 10, -1, -1):
		for cb in range(i * 10, -1, -1):
			dp[ca + a][cb + b] = min(dp[ca + a][cb + b], dp[ca][cb] + c)
ans = 10 ** 18
for ca in range(401):
	for cb in range(401):
		if not ca * Mb == cb * Ma or ca == 0:
			continue
		if ans > dp[ca][cb]:
			ans = dp[ca][cb]
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


(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, a, b) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
INF = 500
dp = [[[INF for i in range(411)] for j in range(411)] for k in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	for j in range(a * n + 1):
		for k in range(b * n + 1):
			if j - l[i][0] >= 0 and k - l[i][1] >= 0:
				dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - l[i][0]][k - l[i][1]] + l[i][2])
			else:
				dp[i + 1][j][k] = dp[i][j][k]
i = 1
ans = INF
while i * max(a, b) <= 400:
	ans = min(ans, dp[n][i * a][i * b])
	i += 1
if ans == INF:
	print(-1)
else:
	print(ans)


(n, ma, mb) = map(int, input().split())
item = [tuple(map(int, input().split())) for _ in range(n)]
INF = 5000
dp = [[INF] * 444 for _ in range(444)]
dp[0][0] = 0
for i in range(n):
	next = [[INF] * 444 for _ in range(444)]
	for j in range(401):
		for k in range(401):
			(a, b, c) = item[i]
			next[j + a][k + b] = min(next[j + a][k + b], dp[j][k] + c)
			next[j][k] = min(next[j][k], dp[j][k])
	dp = next
ans = INF
for i in range(1, 401):
	for j in range(1, 401):
		if ma * j == i * mb:
			ans = min(ans, dp[i][j])
print(ans if ans != INF else -1)


from collections import defaultdict
(N, Ma, Mb) = map(int, input().split())
(INF, MAX) = (1000000000, 10 * N + 1)
dp = defaultdict(lambda : INF)
dp[0, 0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	predp = dp.copy()
	for (ab, v) in predp.items():
		(_a, _b) = ab
		dp[_a + a, _b + b] = min(dp[_a + a, _b + b], v + c)
ans = INF
for i in range(1, N + 1):
	ans = min(ans, dp[Ma * i, Mb * i])
ans = -1 if ans == INF else ans
print(ans)


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


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

def main():
	(N, Ma, Mb) = list(map(int, input().split()))
	INF = int(1000000.0)
	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()


(N, MA, MB) = map(int, input().split())
S = [list(map(int, input().split())) for i in range(N)]
DPLIST = [[10 ** 6 for i in range(401)] for j in range(401)]
DPLIST[0][0] = 0
for (a, b, c) in S:
	for i in range(400, a - 1, -1):
		for j in range(400, b - 1, -1):
			if DPLIST[i][j] > DPLIST[i - a][j - b] + c:
				DPLIST[i][j] = DPLIST[i - a][j - b] + c
ANS = 10 ** 6
for k in range(1, 400 // max(MA, MB)):
	if DPLIST[MA * k][MB * k] < ANS:
		ANS = DPLIST[MA * k][MB * k]
if ANS == 10 ** 6:
	print(-1)
else:
	print(ANS)


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


(n, ma, mb) = list(map(int, input().split()))
(a, b, c) = ([], [], [])
for i in range(n):
	(aa, bb, cc) = list(map(int, input().split()))
	a.append(aa)
	b.append(bb)
	c.append(cc)
dp = [[float('inf')] * (sum(b) + 1) for i in range(sum(a) + 1)]
dp[0][0] = 0
max_a = 0
max_b = 0
for i in range(n):
	max_a += a[i]
	max_b += b[i]
	for ai in range(a[i], max_a + 1)[::-1]:
		for bi in range(b[i], max_b + 1)[::-1]:
			dp[ai][bi] = min(dp[ai][bi], dp[ai - a[i]][bi - b[i]] + c[i])
ans = float('inf')
for i in range(1, min(max_a // ma, max_b // mb)):
	ans = min(ans, dp[i * ma][i * mb])
if ans == float('inf'):
	print(-1)
else:
	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
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]

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]
	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]
	if dp[N - 1][X] == infty:
		print(-1)
	else:
		print(dp[N - 1][X])

def __starting_point():
	main()
__starting_point()


(n, ma, mb) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(n)]
inf = 10 ** 9
lst = [[inf for _ in range(401)] for _ in range(401)]
lst[0][0] = 0
for (a, b, c) in abc:
	for i in range(400, -1, -1):
		if i - a < 0:
			break
		for j in range(400, -1, -1):
			if j - b < 0:
				break
			lst[i][j] = min(lst[i][j], lst[i - a][j - b] + c)
ans = inf
a = ma
b = mb
while 1:
	try:
		ans = min(ans, lst[a][b])
		a += ma
		b += mb
	except IndexError:
		break
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())
S = 411
MAX_N = 10
MAX_SIZE = 400
INF = int(1000000000.0)
dp = [[INF] * S for i in range(S)]
dp[0][0] = 0
for i in range(N):
	for j in range(MAX_SIZE, -1, -1):
		for k in range(MAX_SIZE, -1, -1):
			dp[j + a[i]][k + b[i]] = min((dp[j + a[i]][k + b[i]], dp[j][k] + c[i]))
ans = INF
for i in range(1, MAX_N):
	ans = min((ans, dp[i * Ma][i * Mb]))
if ans == INF:
	print(-1)
else:
	print(ans)


(n, ma, mb) = map(int, input().split())
subs = [list(map(int, input().split())) for _ in range(n)]
infi = 10 ** 18
dp = [[[infi] * 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) = subs[i - 1]
	for j in range(401):
		for k in range(401):
			if j + a <= 400 and k + b <= 400:
				dp[i][j + a][k + b] = min(dp[i][j + a][k + b], dp[i - 1][j][k] + c)
			dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])
ans = infi
for i in range(1, 401):
	for j in range(1, 401):
		if i % ma == 0 and j % mb == 0:
			if i // ma == j // mb:
				ans = min(ans, dp[n][i][j])
if ans == infi:
	ans = -1
print(ans)


(n, ma, mb) = map(int, input().split())
p = []
for i in range(n):
	(a, b, c) = map(int, input().split())
	p.append((a, b, c))
r = [[40001 for j in range(401)] for i in range(401)]
r[0][0] = 0
for i in range(n):
	for j in range(400 - 10 * i, -1, -1):
		for k in range(400 - 10 * i, -1, -1):
			if 40001 > r[j][k]:
				r[j + p[i][0]][k + p[i][1]] = min(r[j + p[i][0]][k + p[i][1]], r[j][k] + p[i][2])
min_v = 40001
ia = ma
ib = mb
flag = False
while ia <= 400 and ib <= 400:
	if 40001 > r[ia][ib] > 0:
		min_v = min(min_v, r[ia][ib])
		flag = True
	ia += ma
	ib += mb
if not flag:
	print(-1)
else:
	print(min_v)


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


def main():
	from collections import defaultdict
	INF = 40 * 100 + 1
	(N, Ma, Mb) = map(int, input().split())
	memo = defaultdict(lambda : INF)
	for _ in range(N):
		(ai, bi, ci) = map(int, input().split())
		x = Ma * bi - Mb * ai
		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)
main()


(n, ma, mb, *L) = map(int, open(0).read().split())
INF = float('inf')
dp = [[INF] * 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 = INF
(_ma, _mb) = (ma, mb)
while _ma < 410 > _mb:
	ans = min(ans, dp[_ma][_mb])
	_ma += ma
	_mb += mb
print(ans if ans < INF else -1)


inf = 9999999999
(N, Ma, Mb) = map(int, input().split())
d = [{} for i in range(N + 1)]
for i in range(N):
	(a, b, c) = map(int, input().split())
	for (j, k) in d[i]:
		d[i + 1][j, k] = d[i][j, k]
	d[i + 1][a, b] = min(c, d[i].get((a, b), inf))
	for (j, k) in d[i]:
		d[i + 1][j + a, k + b] = min(d[i][j, k] + c, d[i].get((j + a, k + b), inf))
ans = inf
for (j, k) in d[N]:
	if j * Mb == k * Ma:
		ans = min(ans, d[N][j, k])
if ans == inf:
	ans = -1
print(ans)


dp_n = 410
(n, ma, mb) = map(int, input().split())
dp = [[float('inf')] * dp_n for _ in range(dp_n)]
dp[0][0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for j in reversed(range(dp_n)):
		for i in reversed(range(dp_n)):
			if dp[i][j] != float('inf'):
				try:
					dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)
				except:
					pass
res = float('inf')
for j in range(1, dp_n):
	for i in range(1, dp_n):
		if i * mb == j * ma:
			res = min(res, dp[i][j])
print(res if res != float('inf') else -1)


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)


from copy import deepcopy
(N, A, B) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(N)]
R = 500
dp = [[10 ** 18] * R for _ in range(R)]
dp[0][0] = 0
for (a, b, c) in ABC:
	newDp = deepcopy(dp)
	for x in range(R):
		for y in range(R):
			if x + a < R and y + b < R:
				newDp[x + a][y + b] = min(newDp[x + a][y + b], dp[x][y] + c)
	dp = newDp
ans = 10 ** 18
for x in range(1, R):
	for y in range(1, R):
		if B * x == A * y:
			ans = min(ans, dp[x][y])
print(ans if ans < 10 ** 18 else -1)


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


(n, ma, mb) = map(int, input().split())
dpn = 400001
dp = [10 ** 6] * dpn
dp[0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for j in range(dpn - 1, -1, -1):
		if j == 0 or dp[j] != 10 ** 6:
			dp[j + a * 1000 + b] = min(dp[j + a * 1000 + b], dp[j] + c)
ans = 10 ** 6
s = 1000 * ma + mb
p = 1
while s * p < dpn:
	ans = min(ans, dp[s * p])
	p += 1
if ans == 10 ** 6:
	print(-1)
else:
	print(ans)


(n, ma, mb) = map(int, input().split())
dp = [[[10 ** 4 for _ in range(401)] for __ in range(401)] for ___ in range(n + 1)]
for i in range(n + 1):
	dp[i][0][0] = 0
for i in range(n):
	(a, b, c) = map(int, input().split())
	for j in range(401):
		for k in range(401):
			if j >= a and k >= b:
				dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - a][k - b] + c)
			else:
				dp[i + 1][j][k] = dp[i][j][k]
ans = float('INF')
for j in range(1, 401):
	for k in range(1, 401):
		if ma * k == mb * j:
			ans = min(ans, dp[n][j][k])
if ans == 10 ** 4:
	print(-1)
else:
	print(ans)


(n, ma, mb) = map(int, input().split())
dp = [[[4001] * 401 for _ in range(401)] for j in range(n + 1)]
dp[0][0][0] = 0
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
	(a[i], b[i], c[i]) = map(int, input().split())
for i in range(n):
	for j in range(401):
		for k in range(401):
			if dp[i][j][k] == 4001:
				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 = 4001
for i in range(1, 401):
	for j in range(1, 401):
		if i * mb == j * ma:
			ans = min(ans, dp[n][i][j])
print(ans if ans != 4001 else -1)


def calc():
	(n, ma, mb) = map(int, input().split())
	dp = [[[5000] * 401 for _ in range(401)] for _ in range(41)]
	arr = [list(map(int, input().split())) for _ in range(n)]
	dp[0][0][0] = 0
	for t in range(n):
		(a, b, c) = arr[t]
		for i in range(401):
			for j in range(401):
				if dp[t][i][j] == 5000:
					continue
				dp[t + 1][i][j] = min(dp[t + 1][i][j], dp[t][i][j])
				dp[t + 1][i + a][j + b] = min(dp[t + 1][i + a][j + b], dp[t][i][j] + c)
	ans = 5000
	for i in range(1, 401):
		if i * ma > 400 or i * mb > 400:
			break
		ans = min(ans, dp[n][i * ma][i * mb])
	if ans == 5000:
		print(-1)
	else:
		print(ans)
calc()


(N, Ma, Mb) = map(int, input().split())
L = []
for _ in range(N):
	L.append(list(map(int, input().split())))
dp = [[[10 ** 10 for _ in range(601)] for _ in range(601)] for _ in range(N + 10)]
dp[0][0][0] = 0
for l in range(N):
	for i in range(200):
		for j in range(200):
			dp[l + 1][i][j] = min(dp[l + 1][i][j], dp[l][i][j])
			dp[l + 1][i + L[l][0]][j + L[l][1]] = min(dp[l + 1][i + L[l][0]][j + L[l][1]], dp[l][i][j] + L[l][2])
ans = 10 ** 10
for i in range(1, 10000):
	try:
		ans = min(ans, dp[N][Ma * i][Mb * i])
	except:
		pass
if ans == 10 ** 10:
	print(-1)
else:
	print(ans)


MX = 401
(N, Ma, Mb) = map(int, input().split())
A = [0] * N
B = [0] * N
C = [0] * N
for i in range(N):
	(a, b, c) = map(int, input().split())
	A[i] = a
	B[i] = b
	C[i] = c
INF = 10 ** 18
dp = [[[INF] * MX for i in range(MX)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(1, N + 1):
	for j in range(0, MX):
		for k in range(0, MX):
			dp[i][j][k] = dp[i - 1][j][k]
			if j < A[i - 1] or k < B[i - 1]:
				continue
			dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - A[i - 1]][k - B[i - 1]] + C[i - 1])
ans = INF
for i in range(1, MX):
	if Ma * i > MX - 1 or Mb * i > MX - 1:
		break
	ans = min(ans, dp[N][Ma * i][Mb * i])
if ans == INF:
	print(-1)
else:
	print(ans)


import sys
input = sys.stdin.readline
(N, Ma, Mb) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(N)]
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):
		if i * Mb == j * Ma:
			ans = min(ans, dp[i][j])
print(ans if ans != inf else -1)


def push(k, v):
	if k in dic:
		dic[k] = min(dic[k], v)
	else:
		dic[k] = v
(n, x, y) = map(int, str(input()).split(' '))
dic = {}
for i in range(0, n):
	a = list(map(int, str(input()).split(' ')))
	(k, v) = (a[0] * y - a[1] * x, a[2])
	l = []
	for j in dic:
		l.append([j, dic[j]])
	for jj in l:
		push(jj[0] + k, jj[1] + v)
	push(k, v)
if 0 in dic:
	print(dic[0])
else:
	print('-1')


(N, Ma, Mb) = map(int, input().split())
INF = 10 ** 18
dp = [[[INF] * (10 * N + 1) for _ in range(10 * N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for j in range(10 * N + 1 - a):
		for k in range(10 * N + 1 - b):
			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):
	if j * Ma > 10 * N or j * Mb > 10 * N:
		break
	ans = min(ans, dp[N][j * Ma][j * Mb])
if ans == INF:
	ans = -1
print(ans)


INF = float('inf')
(N, Ma, Mb) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(N)]
dp = [[[INF] * (10 * N + 11) for _ in range(10 * N + 11)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	for a1 in range(10 * N + 1):
		for b1 in range(10 * N + 1):
			(a, b, c) = abc[i]
			dp[i + 1][a1][b1] = min(dp[i][a1][b1], dp[i][a1 - a][b1 - b] + c)
ans = INF
for a1 in range(1, 10 * N + 1):
	for b1 in range(1, 10 * N + 1):
		if a1 * Mb == b1 * Ma:
			ans = min(ans, dp[N][a1][b1])
if ans == INF:
	ans = -1
print(ans)


(N, Ma, Mb) = map(int, input().split())
C = [map(int, input().split()) for i in range(N)]
INF = 40000
dp = [[[INF] * 401 for i in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(1, N + 1):
	(a, b, c) = C[i - 1]
	for j in range(401):
		for k in range(401):
			dp[i][j][k] = dp[i - 1][j][k]
			if j >= a and k >= b and (dp[i - 1][j - a][k - b] != INF):
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - a][k - b] + c)
ans = INF
(Ma2, Mb2) = (Ma, Mb)
while max(Ma2, Mb2) < 401:
	ans = min(ans, dp[-1][Ma2][Mb2])
	Ma2 += Ma
	Mb2 += Mb
print(ans if ans != INF else -1)


import sys
input = sys.stdin.readline
inf = float('inf')
(N, Ma, Mb) = map(int, input().split())
dp = [[[inf] * 401 for _ in range(401)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	(a, b, c) = map(int, input().split())
	for j in range(401):
		for k in range(401):
			dp[i + 1][j][k] = dp[i][j][k]
			if j - a >= 0 and k - b >= 0 and (dp[i + 1][j][k] > dp[i][j - a][k - b] + c):
				dp[i + 1][j][k] = dp[i][j - a][k - b] + c
ans = inf
for j in range(1, 401):
	for k in range(1, 401):
		if j * Mb == Ma * k and ans > dp[N][j][k]:
			ans = dp[N][j][k]
if ans == inf:
	ans = -1
print(ans)


def getlist():
	return list(map(int, input().split()))
INF = float('inf')
(N, Ma, Mb) = getlist()
L = [[INF] * 401 for i in range(401)]
L[0][0] = 0
for i in range(N):
	(a, b, c) = getlist()
	for j in range(401):
		for k in range(401):
			if L[400 - j][400 - k] != INF:
				L[400 - j + b][400 - k + a] = min(L[400 - j][400 - k] + c, L[400 - j + b][400 - k + a])
ans = INF
x = Ma
y = Mb
while y <= 400 and x <= 400:
	ans = min(ans, L[y][x])
	x += Ma
	y += Mb
if ans == INF:
	print(-1)
else:
	print(ans)


(N, Ma, Mb) = map(int, input().split())
dp = [[[10 ** 9] * 401 for i in range(401)] for i in range(N)]
for i in range(N):
	(a, b, c) = map(int, input().split())
	if i == 0:
		dp[0][a][b] = c
		dp[0][0][0] = 0
	else:
		for p in range(401):
			for q in range(401):
				if p >= a and q >= b:
					dp[i][p][q] = min(dp[i - 1][p][q], dp[i - 1][p - a][q - b] + c)
				else:
					dp[i][p][q] = dp[i - 1][p][q]
ans = 10 ** 9
for a in range(1, 401):
	if Mb * a / Ma <= 400 and Mb * a % Ma == 0:
		ans = min(ans, dp[N - 1][a][Mb * a // Ma])
if ans == 10 ** 9:
	print(-1)
else:
	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)


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)


from collections import defaultdict
(n, ma, mb) = map(int, input().split())
f = defaultdict(lambda : float('inf'))
for _ in range(n):
	(a, b, c) = map(int, input().split())
	t = f.copy()
	t[a, b] = min(t[a, b], c)
	for (k, v) in f.items():
		(ka, kb) = (k[0] + a, k[1] + b)
		t[ka, kb] = min(t[ka, kb], v + c)
	f = t
costs = [f[a, b] for (a, b) in f if a * mb == b * ma]
print(min(costs) if costs else -1)


(N, MA, MB) = map(int, input().split())
src = [tuple(map(int, input().split())) for i in range(N)]
INF = 10 ** 9
MAX = 401
dp = [[INF] * MAX for i in range(MAX)]
dp[0][0] = 0
amax = bmax = 0
for (a, b, n) in src:
	for i in reversed(range(bmax + 1)):
		for j in range(amax + 1):
			if dp[i][j] == INF:
				continue
			dp[i + b][j + a] = min(dp[i + b][j + a], dp[i][j] + n)
	amax += a
	bmax += b
ans = INF
for i in range(1, MAX):
	if i * MA >= MAX or i * MB >= MAX:
		break
	ans = min(ans, dp[i * MB][i * MA])
print(-1 if ans == INF else ans)