Buggy python submission (verdict: Runtime Error):
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
INF = 100000
from collections import defaultdict as dd
dp =  [dd(lambda:INF) for _ in range(N+1)]#dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
for n in range(1,N+1):
    a,b,c = Med[n-1]
    dp[n-1][0,0] = 0
    for (i,j),value in dp[n-1].items():
        dp[n][i+a,j+b] = min(dp[n-1][i+a,j+b],value+c)

ans = INF
for (i,j),value in dp[N].items():
    if i == j == 0:
        continue
    if i*Mb == j*Ma:
        ans = min(ans, value)
print(ans if ans != INF else -1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
INF = 100000
dp = [[INF]*(N+1) for _ in range(N+1)] #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0][0] = 0 
from itertools import product as prd
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in prd(R(a),R(b)):
        dp[i][j] = min(dp[i][j], dp[i-a][j-b]+c)

ans = INF
for i,j in prd(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i][j])
print(ans if ans != INF else -1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Runtime Error):
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
INF = 100000
dp = [[INF]*N+1 for _ in range(N+1)] #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0][0] = 0 
from itertools import product as prd
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in prd(R(a),R(b)):
        dp[i][j] = min(dp[i][j], dp[i-a][j-b]+c)

ans = INF
for i,j in prd(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i][j])
print(ans if ans != INF else -1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
INF = 100000
import numpy as np
dp = np.full((N+1,N+1),INF,dtype='int64') #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0,0] = 0 
from itertools import product as prd
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in prd(R(a),R(b)):
        dp[i,j] = min(dp[i,j], dp[i-a,j-b]+c)

ans = INF
for i,j in prd(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i,j])
print(ans if ans != INF else -1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
import numpy as np
dp = np.full((N+1,N+1),np.inf) #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0,0] = 0 
from itertools import product
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in product(R(a),R(b)):
        dp[i,j] = min(dp[i,j], dp[i-a,j-b]+c)

ans = np.inf
for i,j in product(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i,j])
print(int(ans) if ans != np.inf else -1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
import math
nmax = 40
abmax = 10
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)

dp = {}
#dp初期化
for i in range(N+1):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            dp[i,ca,cb] = INF
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:
                dp[i+1,ca,cb] = min(dp[i+1,ca,cb],dp[i,ca,cb])
                dp[i+1,ca+medichine[i][0],cb+medichine[i][1]] = min(dp[i+1,ca+medichine[i][0],cb+medichine[i][1]], dp[i,ca,cb]+medichine[i][2])

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)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, a, b, c, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], [a[n], b[n], c[n]]]
        if a[n] * Mb == b[n] * Ma:
            cost = c[n]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, a, b, c, Ma, Mb)
        List = previous[0].copy()
        cost = previous[1]
        for x in previous[0]:
            C = x[2] + c[n]
            if C < cost:
                A = x[0] + a[n]
                B = x[1] + b[n]
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C         
    return List, cost


N, Ma, Mb = map(int, input().split())
a, b, c = [], [], []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    a.append(Lst[0])
    b.append(Lst[1])
    c.append(Lst[2])
ans = dp(N-1, a, b, c, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[n]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[n][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0].copy()
        cost = previous[1]
        if medichine[n][2] < cost:
            for x in previous[0]:
                C = x[2] + medichine[n][2]
                if C > cost:
                    continue
                A = x[0] + medichine[n][0]
                B = x[1] + medichine[n][1]
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C         
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[0][0] * Mb == medichine[0][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0].copy()
        cost = previous[1]
        for x in previous[0]:
            C = x[2] + medichine[n][2]
            if C < cost:
                A = x[0] + medichine[n][0]
                B = x[1] + medichine[n][1]
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C         
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            if C < cost:
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = {}
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine[i] = Lst
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            if C < cost:
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C
        del previous
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            if C < cost:
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            List.append([A, B, C])
            if A * Mb == B * Ma:
                cost = min(cost, C)
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF =  5000

N, Ma, Mb = map(int, input().split())
a, b, c = [], [], []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    a.append(Lst[0])
    b.append(Lst[1])
    c.append(Lst[2])

cost = INF
for n in range(1,2**N):
    A, B, C = 0, 0, 0
    for i in range(N):
        if n & (1<<i):
            A += a[i]
            B += b[i]
            C += c[i]
            if C > cost:
                break
    if A * Mb == B * Ma:
        cost = min(cost, C)
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
#bit全探索する
INF =  5000

N, Ma, Mb = map(int, input().split())
a, b, c = [], [], []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    a.append(Lst[0])
    b.append(Lst[1])
    c.append(Lst[2])

cost = INF
for n in range(1,2**N):
    A, B, C = 0, 0, 0
    for i in range(N):
        if n & (1<<i):
            A += a[i]
            B += b[i]
            C += c[i]
    if A * Mb == B * Ma:
        cost = min(cost, C)
if cost != INF:
    print(cost)
else:
    print(-1)

Fixed submission:
import collections
import copy
INF = 10000

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

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

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

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