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.



Sample input:
3 1 1
1 2 1
2 1 2
3 3 10


Sample output:
3

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Ma, Mb = map(int, input().split())
l = [[0] * 3 for i in range(N)]
for i in range(N):
    l[i][0], l[i][1], l[i][2] = map(int, input().split())

memo = [[[INF] * 11  for i in range(11)] for i in range(N+1)]
def dfs(cur, a, b, c):
    if memo[cur][a][b] != INF:
        return memo[cur][a][b]
    if cur == N:
        return INF
    mn = INF
    if b != 0 and a / b == Ma / Mb:
        mn = min(c, mn)
    mn = min(dfs(cur+1, a+l[cur][0], b+l[cur][1], c+l[cur][2]), mn)
    mn = min(dfs(cur+1, a, b, c), mn)
    memo[cur][a][b] = mn
    return mn

ans = dfs(0, 0, 0, 0)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = (list)(map(int, input().split()))
l = []
inf = 10**6
dp = [[[inf]*402 for _ in range(402)] for _ in range(40)]


for _ in range(N):
    l.append((list)(map(int, input().split())))

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

for i in range(N):
    for ca in range(401):
        for cb in range(401):
            if dp[i][ca][cb] != inf:
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
                t_a = l[i][0]
                t_b = l[i][1]
                dp[i+1][ca+t_a][cb+t_b] =\
                    min(dp[i+1][ca+t_a][cb+t_b], dp[i][ca][cb]+l[i][2])

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

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

Submission status: Runtime Error

Solution code:
N, Ma, Mb = (list)(map(int, input().split()))
l = []
inf = 10**6
dp = [[[inf]*402 for _ in range(402)] for _ in range(40)]


for _ in range(N):
    l.append((list)(map(int, input().split())))

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

for i in range(N):
    for ca in range(401):
        for cb in range(401):
            if dp[i][ca][cb] != inf:
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
                t_a = l[i][0]
                t_b = l[i][1]
                dp[i+1][ca+t_a][cb+t_b] =\
                    min(dp[i+1][ca+t_a][cb+t_b], dp[i][ca][cb]+l[i][2])

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)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = (list)(map(int, input().split()))
N_max = 40
abmax = 10
l = []
inf = 10**6
dp = [[[inf]*401 for _ in range(401)] for _ in range(40)]


for _ in range(N):
    l.append((list)(map(int, input().split())))

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

for i in range(N):
    for ca in range(401):
        for cb in range(401):
            if dp[i][ca][cb] != inf:
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
                t_a = l[i][0]
                t_b = l[i][1]
                dp[i+1][ca+t_a][cb+t_b] =\
                    min(dp[i+1][ca+t_a][cb+t_b], dp[i][ca][cb]+l[i][2])

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)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = (list)(map(int, input().split()))
N_max = 40
abmax = 10
l = []
inf = 10**6
dp = [[[inf]*401 for _ in range(401)] for _ in range(40)]


for _ in range(N):
    l.append((list)(map(int, input().split())))

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

for i in range(N):
    for ca in range(401):
        for cb in range(401):
            if dp[i][ca][cb] != inf:
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
                t_a = l[i][0]
                t_b = l[i][1]
                dp[i+1][ca+t_a][cb+t_b] =\
                    min(dp[i+1][ca+t_a][cb+t_b], dp[i][ca][cb]+l[i][2])

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

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

Submission status: Runtime Error

Solution code:
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 40)] for _ in range(b_sum + 40)] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum):
        for b in range(b_sum):
            if dp[i + 1][a][b] > dp[i][a][b]:
                dp[i + 1][a][b] = dp[i][a][b]
            if dp[i + 1][a + items[i][0]][b + items[i][1]] > dp[i][a][b] + items[i][2]:
                dp[i + 1][a + items[i][0]][b + items[i][1]] = dp[i][a][b] + items[i][2]

ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 20)] for _ in range(b_sum + 20)] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum):
        for b in range(b_sum):
            if dp[i + 1][a][b] > dp[i][a][b]:
                dp[i + 1][a][b] = dp[i][a][b]
            if dp[i + 1][a + items[i][0]][b + items[i][1]] > dp[i][a][b] + items[i][2]:
                dp[i + 1][a + items[i][0]][b + items[i][1]] = dp[i][a][b] + items[i][2]

ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

inf = float("inf")
dp = [[[inf for _ in range(401)] for _ in range(401)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(401):
        for b in range(401):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, 401):
    for b in range(1, 401):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 40)] for _ in range(b_sum + 40)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 20)] for _ in range(b_sum + 20)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 11)] for _ in range(b_sum + 11)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

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

dp = [[[float("inf") for _ in range(401)] for _ in range(401)] for _ in range(N+1)]
dp[0][0][0] = 0



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

Submission status: Runtime Error

Solution code:
N, Ma, Mb= (int(i) for i in input().split())
L = []
for i in range(N):
    a, b, c = (int(i) for i in input().split())
    L.append((a-1, b-1, c))

dp= [[[float("inf")] * (10 * N + 11) for a in range(10 * N + 11) ] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N + 1):
    a, b, c = L[i]
    for ca in range(10 * N + 1):
        for cb in range(10 * N + 1):
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            dp[i+1][ca + a][cb + b] = min(dp[i+1][ca + a][cb + b], dp[i][ca][cb] + c)

reslis = []
ra, rb = (Ma, Mb)
while ra <= 10 * N and rb <= 10 * N:
    reslis.append(dp[N][ra][rb])
    ra += Ma
    rb += Mb

reslis.sort()
res = reslis[0]
if res == float("inf"):
    print(-1)
else:
    print(res)

Submission status: Runtime Error

Solution code:
N, Ma, Mb= (int(i) for i in input().split())
L = []
for i in range(N):
    a, b, c = (int(i) for i in input().split())
    L.append((a-1, b-1, c))

dp= [[[float("inf") for b in range(10 * N + 1)] for a in range(10 * N + 1) ] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N):
    a, b, c = L[i]
    for ca in range(10 * N + 1):
        for cb in range(10 * N + 1):
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            dp[i+1][ca + a][cb + b] = min(dp[i+1][ca + a][cb + b], dp[i][ca][cb] + c)

reslis = []
ra, rb = (Ma, Mb)
while ra <= 10 * N and rb <= 10 * N:
    reslis.append(dp[N][ra][rb])
    ra += Ma
    rb += Mb

reslis.sort()
res = reslis[0]
if res == float("inf"):
    print(-1)
else:
    print(res)

Submission status: Runtime Error

Solution code:
import itertools
import numpy
N, Ma, Mb = map(int, input().split())
r = Ma/Mb
costlist = []
data = [list(map(int, input().split())) for i in range(N)]
for i in range(1, max(N+1, 11)):
    combination = numpy.array(list(itertools.combinations(data, i)))
    for k in range(len(combination)):
        a_tot = 0
        b_tot = 0
        c_tot = 0
        for j in range(len(combination[k])):
            a_tot += combination[k][j][0]
            b_tot += combination[k][j][1]
            c_tot += combination[k][j][2]
        if a_tot/b_tot == r:
            costlist.append(c_tot)
if costlist == []:
    print(-1)
else:
    print(min(costlist))

Submission status: Runtime Error

Solution code:
N,ma,mb = map(int,raw_input().split())

a=[]
b=[]
c=[]
for i in range(N):
	at,bt,ct=map(int,raw_input().split())

	a.append(at)
	b.append(bt)
	c.append(ct)
	

dp = [[[10**10 for i in range(400+1)] for j in range(400+1)] for k in range(N+1)]
dp[0][0][0]=0
for i in range(N):
	for j in range(401):
		for k in range(401):
			if(dp[i][j][k]<10**10):
				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])

int ans=10**10

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>=10**10:
	print -1
else:
	print ans

Submission status: Runtime Error

Solution code:
N,Ma,Mb = map(int,input().split())
first_half = []
last_half = []
for i in range(N):
	a,b,c = map(int,input().split())
	if i < N // 2:
		first_half.append((a,b,c))
	else:
		last_half.append((a,b,c))

first_half_combination = {}
last_half_combination = {}
def make_all_combination(i,a,b,c,d_list,flag):
	if i == len(d_list):
		if c == 0:
			return

		w = Ma * b - Mb * a
		if flag:
			if w not in first_half_combination or c < first_half_combination[w]:
				first_half_combination[w] = c
		else:
			if -w not in last_half_combination or c < last_half_combination[-w]:
				last_half_combination[-w] = c
		return
	make_all_combination(i+1,a,b,c,d_list,flag)
	make_all_combination(i+1,a+d_list[i][0],b+d_list[i][1],c+d_list[i][2],d_list,flag)

make_all_combination(0,0,0,0,first_half,True)
make_all_combination(0,0,0,0,last_half,False)

INF = 10**8
f_0 = first_half_combination[0] if 0 in last_half_combination else INF
l_0 = first_half_combination[0] if 0 in last_half_combination else INF
ans = min(f_0,l_0) if min(f_0,l_0) < INF else -1
for w in first_half_combination.keys():
	if w == 0:
		continue
	if w in last_half_combination:
		cost = first_half_combination[w] + last_half_combination[w]
		if w == 0:
			cost = min(first_half_combination[w], last_half_combination[w])
		if ans == -1 or cost < ans:
			ans = cost
print(ans)

Submission status: Runtime Error

Solution code:
N,Ma,Mb = map(int,input().split())
first_half = []
last_half = []
for i in range(N):
	a,b,c = map(int,input().split())
	if i < N // 2:
		first_half.append((a,b,c))
	else:
		last_half.append((a,b,c))

first_half_combination = {}
last_half_combination = {}
def make_all_combination(i,a,b,c,d_list,flag):
	if i == len(d_list) and c > 0:
		w = Ma * b - Mb * a
		if flag:
			if w not in first_half_combination or c < first_half_combination[w]:
				first_half_combination[w] = c
		else:
			if -w not in last_half_combination or c < last_half_combination[-w]:
				last_half_combination[-w] = c
		return
	make_all_combination(i+1,a,b,c,d_list,flag)
	make_all_combination(i+1,a+d_list[i][0],b+d_list[i][1],c+d_list[i][2],d_list,flag)

def search(w, lst):
	left,right = 0, len(lst)
	while left + 1 != right:
		p = (left + right) // 2
		if lst[p][0] < w:
			left = p
		else:
			right = p
	return left
make_all_combination(0,0,0,0,first_half,True)
make_all_combination(0,0,0,0,last_half,False)

print(first_half_combination)
print(last_half_combination)
ans = -1
for w in first_half_combination.keys():
	if w in last_half_combination:
		cost = first_half_combination[w] + last_half_combination[w]
		if w == 0:
			cost = min(first_half_combination[w], last_half_combination[w])
		if ans == -1 or cost < ans:
			ans = cost
	elif w == 0:
		cost = first_half_combination[w]
		if cost < ans:
			ans = cost
print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
using namespace std;

const int max_n = 40, max_ab = 10, INF = 100001;

int a[max_n], b[max_n], c[max_n];
int dp[max_n + 1][max_n*max_ab + 1][max_n*max_ab + 1];


int main()
{
	int n, ma, mb;
	cin >> n >> ma >> mb;

	for (int i = 0;i < n;i++) {
		cin >> a[i] >> b[i] >> c[i];
	}

	for (int i = 0;i <= n;i++) {
		for (int j = 0;j <= n * max_ab;j++) {
			for (int k = 0;k <= n * max_ab;k++) {
				dp[i][j][k] = INF;
			}
		}
	}

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

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n * max_ab;j++) {
			for (int k = 1;k <= n * max_ab;k++) {
				if (a[i - 1] <= j && b[i - 1] <= k) {
					dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a[i - 1]][k - b[i - 1]] + c[i - 1]);
				}
				else dp[i][j][k] = dp[i - 1][j][k];
			}
		}
	}

	int min_cost = INF;
	for (int i = 1;i <= n * max_ab;i++) {
		for (int j = 1;j <= n * max_ab;j++) {
			if (i * mb == j * ma) min_cost = min(min_cost, dp[n][i][j]);
		}
	}

	if (min_cost == INF) cout << -1 << endl;
	else cout << min_cost << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
from functools import reduce

N, Ma, Mb = map(int, input().split())
X = np.array([list(map(int, input().split())) for _ in range(N)])
z = []

def update_z(_y, index2):
    tmp = reduce(lambda a,b:a+b, [x for k,x in enumerate(X) if k in index2])
    if tmp[0]*Mb == tmp[1]*Ma:
        z.append(min(_y, tmp[2]))

def rec(y=4001, i=0, index=None):
    if i<N:
        if index:
            for j in range(i,N):
                update_z(y, index+[j])
                rec(y, j+1, index + [j])
        else:
            for j in range(i,N):
                update_z(y, [j])
                rec(y, j+1, [j])

rec()
print(-1 if min(z)>4000 else min(z))

Submission status: Runtime Error

Solution code:
from itertools import combinations
N, Ma, Mb = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]
c_max = abc[np.array([_i[2] for _i in abc], dtype='int8').argmax()]
min_cost = -1
for _i in range(1, N+1):
    all_pattern = list(combinations(range(N), _i))
    for _j in all_pattern:
        _a = sum([abc[_k][0] for _k in _j])
        _b = sum([abc[_k][1] for _k in _j])
        _c = sum([abc[_k][2] for _k in _j])
        if _b * Ma == _a * Mb:
            if min_cost == -1 or min_cost > _c:
                min_cost = _c
print(min_cost)

Submission status: Runtime Error

Solution code:
N, Ma, Mb = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]
from itertools import combinations
c_max = abc[np.array([_i[2] for _i in abc], dtype='int8').argmax()]
min_cost = -1
for _i in range(1, N+1):
    all_pattern = list(combinations(range(N), _i))
    for _j in all_pattern:
        _a = sum([abc[_k][0] for _k in _j])
        _b = sum([abc[_k][1] for _k in _j])
        _c = sum([abc[_k][2] for _k in _j])
        if _b * Ma == _a * Mb:
            if min_cost == -1 or min_cost > _c:
                min_cost = _c
print(min_cost)

Submission status: Runtime Error

Solution code:
n, ma, mb = map(int, f.readline().split())
a, b, c = [], [], []
for _ in range(n):
    at, bt, ct = map(int, f.readline().split())
    a.append(at)
    b.append(bt)
    c.append(ct)
    
dp = [[float('inf') for _ in range(n*mb + 1)] for _ in range(n*ma + 1)]
dp[0][0] = 0
used = [[0, 0]]

for i in range(n):
    add_used = []
    for at, bt in used:
        if at+a[i] <= n and bt+b[i] <= n:
            if dp[at+a[i]][bt+b[i]] == float('inf'):
                add_used.append([at+a[i], bt+b[i]])
            
            dp[at+a[i]][bt+b[i]] = min(dp[at][bt]+c[i], dp[at+a[i]][bt+b[i]])
        
    used += add_used

if dp[-1][-1] == float('inf'):
    print(-1)
else :
    print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
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 i in range(N):
    DP2 = [[INF]*(411) for _ in range(411)]
    a, b, c = inpl()
    for i in range(10*(i+1) + 1):
        for j in range(10*(i+1) + 1):
            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)

Submission status: Runtime Error

Solution code:
n,ma,mb=map(int,input().split())
lista=[]
listb=[]
listc=[]
for i in range(n):
    a,b,c=map(int,input().split())
    lista.append(a)
    listb.append(b)
    listc.append(c)
x=sum(lista)
y=sum(listb)
z=0
w=0
dp=[[[float('inf') for i in range(n+1)]for i\
 in range(y+1)]for i in range(x+1)]
for i in range(n+1):
    dp[0][0][i]=0
for i in range(1,n+1):
    z+=lista[i-1]
    y+=listb[i-1]
    for a in range(z+1):
        for b in range(w+1):
            if a-lista[i-1]>=0 and b-listb[i-1]>=0:
                dp[a][b][i]=min(dp[a][b][i-1],dp[a-lista[i-1]][b-listb[i-1]][i-1]+listc[i-1])
            else:
                dp[a][b][i]=dp[a][b][i-1]
cost=float('inf')
for a in range(1,x+1):
    if float.is_integer(a*mb/ma) and a*mb/ma<=y+1:
            cost=min(cost,dp[a][int(a*mb/ma)][n])
if cost==float('inf'):
    print(-1)
else:
    print(cost)

Submission status: Runtime Error

Solution code:
n,ma,mb=map(int,input().split())
lista=[]
listb=[]
listc=[]
for i in range(n):
    a,b,c=map(int,input().split())
    lista.append(a)
    listb.append(b)
    listc.append(c)
x=sum(lista)
y=sum(listb)
z=0
w=0
dp=[[[float('inf') for i in range(n+1)]for i\
 in range(y+1)]for i in range(x+1)]
for i in range(n+1):
    dp[0][0][i]=0
for i in range(1,n+1):
    if i==n:
        continue
    else:
        z+=lista[i-1]
        y+=listb[i-1]
    for a in range(z+1):
        for b in range(w+1):
            if a-lista[i-1]>=0 and b-listb[i-1]>=0:
                dp[a][b][i]=min(dp[a][b][i-1],dp[a-lista[i-1]][b-listb[i-1]][i-1]+listc[i-1])
            else:
                dp[a][b][i]=dp[a][b][i-1]
cost=float('inf')
for a in range(1,x+1):
    if float.is_integer(a*mb/ma) and a*mb/ma<=y+1:
            cost=min(cost,dp[a][int(a*mb/ma)][n])
if cost==float('inf'):
    print(-1)
else:
    print(cost)

Submission status: Runtime Error

Solution code:
n,ma,mb=map(int,input().split())
lista=[]
listb=[]
listc=[]
for i in range(n):
    a,b,c=map(int,input().split())
    lista.append(a)
    listb.append(b)
    listc.append(c)
dp=[[[float('inf') for i in range(n+1)]for i\
 in range(sum(listb)+1)]for i in range(sum(lista)+1)]
dp[0][0][0]=0
for i in range(1,n+1):
    for a in range(lista[i-1],sum(lista)+1):
        for b in range(listb[i-1],sum(listb)+1):
            dp[a][b][i]=min(dp[a][b][i-1],dp[a-lista[i-1]][b-listb[i-1]][i-1]+listc[i-1])

cost=float('inf')
for a in range(1,sum(lista)):
    for b in range(1,sum(listb)):
        if a*mb==b*ma:
            cost=min(cost,dp[a][b][n])
if cost=float('inf'):
    print(-1)
else:
    print(cost)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
    if a<b:
        a,b = b,a
    if b == 0:
        return a
    c = a%b
    return gcd(b,c)

dp = []
dp.append({(0,0):0})
N,A,B = map(int,input().split())

for i in range(N):
    a,b,c = map(int,input().split())
    temp = dp[-1].copy()
    for key in dp[-1].keys():
        left = key[0] + a
        right = key[1] + b
        g = gcd(left, right)
        if g != 1:
            left = int(left/g)
            right = int(right/g)
        n_key = (left,right)
        if not (n_key in temp):
            temp[n_key] = dp[-1][key]+c
        elif dp[-1][key]+c < dp[-1][n_key]:
            temp[n_key] = dp[-1][key]+c
    dp.append(temp)

if (A,B) in dp[N-1]:
    print(dp[N-1][(A,B)])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math
dp = []
dp.append({(0,0):0})

N,A,B = map(int,input().split())

for i in range(N):
    a,b,c = map(int,input().split())
    temp = dp[-1].copy()
    for key in dp[-1].keys():
        left = key[0] + a
        right = key[1] + b
        g = math.gcd(left, right)
        if g != 1:
            left = int(left/g)
            right = int(right/g)
        n_key = (left,right)
        if not (n_key in temp):
            temp[n_key] = dp[-1][key]+c
        elif dp[-1][key]+c < dp[-1][n_key]:
            temp[n_key] = dp[-1][key]+c
    dp.append(temp)

if (A,B) in dp[N-1]:
    print(dp[N-1][(A,B)])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N,Ma,Mb=map(int,input().split())
Med=[]
cnt_a=0
cnt_b=0
for i in range(N):
  a=[int(x) for x in input().split()]
  Med.append(a)
  cnt_a+=a[0]
  cnt_b+=a[1]
  
#[i]まででMa=[j],Mb=[k]を作る場合の最小のコストdp
#dp[i+1][j+Ma][k+Mb]=min(dp[i][j+Ma][k+Mb],dp[i][j][k]+Cost)
#リストをinfで初期化。inf=作れない配合なので、continue。初期値はdp[0][0][0]=0
dp=[[[float('inf') for j in range(cnt_b+1)] for k in range(cnt_a+1)] for i in range(N+1)]
dp[0][0][0]=0

for i in range(N):
  for j in range(cnt_a+1):
    for k in range(cnt_b+1):
      if dp[i][j][k]==float('inf'):
        continue
      dp[i+1][j][k]=min(dp[i][j][k],dp[i+1][j][k])
      dp[i+1][j+Med[i][0]][k+Med[i][1]]=min(dp[i][j+Med[i][0]][k+Med[i][1]],dp[i][j][k]+Med[i][2])

ans=float('inf')
for i in range(1,N+1):
  if i*Ma<401 and i*Mb<401:
    ans=min(ans,dp[N][i*Ma][i*Mb])
if ans==float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10000)
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))
 
def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)
 
def dfs(i, v, r,ans):
    if i == n:
        if r == (Ma,Mb):
            ans.append(v)
        return 0
 
    if dfs(i+1, v, r,ans):
        return 0
    
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])), ans):
        return 0
 
    return 0
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]
 
def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(5000)
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))
 
def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)
 
def dfs(i, v, r,ans):
    if i == n:
        if r == (Ma,Mb):
            ans.append(v)
        return 0
 
    if dfs(i+1, v, r,ans):
        return 0
    
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])), ans):
        return 0
 
    return 0
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]
 
def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit
setrecursionlimit(5000)
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))
 
def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)
 
def dfs(i, v, r,ans):
    if i == n:
        if r == (Ma,Mb):
            ans.append(v)
        return 0

    if dfs(i+1, v, r,ans):
        return 0
    
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])), ans):
        return 0
 
    return 0
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]

def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
setrecursionlimit
setrecursionlimit(5000)
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))
 
def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)
 
def dfs(i, v, r,ans):
    if i == n:
        if r == (Ma,Mb):
            ans.append(v)
        return 0

    if dfs(i+1, v, r,ans):
        return 0
    
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])), ans):
        return 0
 
    return 0
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]

def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)
 
if __name__ == "__main__":
    main()