Submission #4046141

---

Source Code Expand

N, Ma, Mb = (list)(map(int, input().split()))
l = []
inf = 10**6
dp = [[[inf]*401 for _ in range(401)] for _ in range(41)]


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 Info

Judge Result