Problem:
 Score : 400 points    Problem Statement 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 1 3 1 1
1 2 1
2 1 2
3 3 10      Sample Output 1 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.       Sample Input 2 1 1 10
10 10 10      Sample Output 2 -1  The ratio 1:10 of the two substances A and B cannot be satisfied by purchasing any combination of the packages. Thus, the output should be -1 .

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
N, Ma, Mb = map(int, input().split())
a = [0]*N
b = [0]*N
c = [0]*N
INF = 10000


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



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

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

ans = INF

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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

sumA = sum([ABC[i][0] for i in range(N)])
sumB = sum([ABC[i][1] for i in range(N)])

INF = 10 ** 15
dp = [[INF for j in range(sumB + 1)] for i in range(sumA + 1)]
dp[0][0] = 0

for a, b, c in ABC:
  for i in range(sumA, -1, -1):
    for j in range(sumB, -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, sumA + 1):
  for j in range(1, sumB + 1):
    if dp[i][j] != INF and i / j == Ma / Mb:
      answer = min(answer, dp[i][j])
      
print(answer if answer != INF else -1)

Solution (Python):
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)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e09)


def main():
    
    N, Ma, Mb = Scanner.map_int()
    A = [0] * N
    B = [0] * N
    C = [0] * N

    for i in range(N):
        a, b, c = Scanner.map_int()
        A[i], B[i], C[i] = a, b, c
    dp = [[[INF for _ in range(401)] for _ in range(401)] for _ in range(41)]
    dp[0][0][0] = 0
    for i in range(N):
        for j in range(401):
            for k in range(401):
                if dp[i][j][k] == INF:
                    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 i in range(1, 401):
        for j in range(1, 401):
            if dp[N][i][j] == INF:
                continue
            if Ma * j == Mb * i:
                ans = min(ans, dp[N][i][j])
    if ans == INF:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

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

items = []
mas = []
mbs = []
costs = []
for i in range(N):
  ma, mb, c = map(int, input().split())
  mas.append(ma)
  mbs.append(mb)
  costs.append(c)

max_cost = 5000
dp = [[[max_cost for k in range((N+1)*10)] for j in range((N+1)*10)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
  for j in range(N*10):
    for k in range(N*10):
      if dp[i][j][k] == max_cost:
        continue
      if dp[i+1][j][k] > dp[i][j][k]:
        dp[i+1][j][k] = dp[i][j][k]
      if dp[i+1][j+mas[i]][k+mbs[i]] > dp[i][j][k] + costs[i]:
        dp[i+1][j+mas[i]][k+mbs[i]] = dp[i][j][k] + costs[i]
        
min_cost = max_cost
for wa in range(1, N*10):
  for wb in range(1, N*10):
    if (wa * Mb != wb * Ma):
      continue;
    if min_cost > dp[N][wa][wb]:
      min_cost = dp[N][wa][wb]

  
if min_cost == max_cost:
  print("-1")
else:
  print(min_cost)

Solution (Python):
import fractions


def args():
    N, MA, MB = list(map(int, input().split()))

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

    
    
    
    

    return N, MA, MB, A, B, C

def solve(N, MA, MB, A, B, C):
    def recur(i, a, b):
        if not MEMO[i][a][b] is None:
            return MEMO[i][a][b]

        if not i < N:
            if 0 < a and 0 < b:
                g = fractions.gcd(a, b)
                if (MA, MB) == (a / g, b / g):
                    return 0
            return float("inf")

        res = min(recur(i + 1, a, b) + 0, recur(i + 1, a + A[i], b + B[i]) + C[i])
        MEMO[i][a][b] = res
        return res

    x, y, z = N + 1, 10 * N + 1, 10 * N + 1
    MEMO = [[[None] * z for _ in range(y)] for _ in range(x)]

    ans = recur(0, 0, 0)

    return ans


if __name__ == '__main__':
    res = solve(*args())

    print(-1) if res == float("inf") else print(res)

Solution (Python):
N,Ma,Mb = map(int,input().split())
dp = [[[10**9 for i in range(401)] for j in range(401)] for k 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(401):
        for k in range(401):
            if j < a:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                if k < b:
                    dp[i][j][k] = dp[i-1][j][k]
                else:
                    dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b] + c)
m = max(Ma,Mb)
import math
n = math.floor(400 / m)
ans = 10**9
for i in range(1,400):
    x = Ma*i
    y = Mb*i
    if x > 400:
        break
    if y > 400:
        break
    ans = min(dp[N][x][y],ans)
if ans == 10**9:
    print(-1)
    quit()
print(ans)

Solution (Python):
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)

Solution (Python):
N,Ma,Mb=[int(x) for x in input().split()]
A=[]
B=[]
C=[]
for i in range(N):
	a,b,c=[int(x) for x in input().split()]
	A.append(a)
	B.append(b)
	C.append(c)


ANS=[[[-1 for k in range(401)] for j in range(401)] for i in range(41)]

INF=1000000000000000000000

def f(ind,wa,wb):
	global Ma
	global Mb
	global N
	if ANS[ind][wa][wb]==-1:
		if ind==0:
			if (wa+A[0])*Mb==(wb+B[0])*Ma:
				ANS[ind][wa][wb] = C[0]
			elif wa*Mb==wb*Ma and (wa!=0 and wb!=0):
				ANS[ind][wa][wb] = 0
			else:
				ANS[ind][wa][wb] = INF
		else:
			ANS[ind][wa][wb] = min(f(ind-1,wa,wb),f(ind-1,wa+A[ind],wb+B[ind])+C[ind])
	return ANS[ind][wa][wb]

ans=f(N-1,0,0)

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

Solution (Python):
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)

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

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

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

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

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

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

Solution (Python):
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
	ua = ub = 15
	for a, b, c in zip(*[iter(L)] * 3):
		for i in range(ua, -1, -1):
			for j in range(ub, -1, -1):
				t = dp[i][j] + c
				if dp[i + a][j + b] > t:
					dp[i + a][j + b] = t
					if ua < i + a:
						ua = i + a
					if ub < j + b:
						ub = j + b
	ans = M
	_ma, _mb = ma, mb
	while _ma < 410 > _mb:
		ans = min(ans, dp[_ma][_mb])
		_ma += ma
		_mb += mb
	print(ans if ans < M else -1)


if __name__ == "__main__":
	main()

Solution (Python):
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)

if __name__=="__main__":
	main()

Solution (Python):
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)

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

Solution (Python):
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

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
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')

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, Y = MAP()
ABC = []
for i in range(N):
    a, b, c = MAP()
    ABC.append((a, b, c))

MAX = 407

dp = list3d(N+1, MAX, MAX, INF)
dp[0][0][0] = 0
for i in range(N):
    a, b, c = ABC[i]
    for j in range(MAX):
        for k in range(MAX):
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            if j+a < MAX and k+b < MAX:
                dp[i+1][j+a][k+b] = min(dp[i+1][j+a][k+b], dp[i][j][k] + c)

j = X
k = Y
ans = INF
while j < MAX and k < MAX:
    
    ans = min(ans, dp[N][j][k])
    j += X
    k += Y
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
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)

Solution (Python):
def main():
    N, Ma, Mb = map(int, input().split())
    A = []
    B = []
    C = []
    for _ in range(N):
        a, b, c = 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)
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, Ma, Mb = map(int, input().split())
    A = []
    B = []
    C = []
    for _ in range(N):
        a, b, c = 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)
    
if __name__ == '__main__':
    main()

Solution (Python):
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)