Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

Z1 = list(product([0,1],repeat=N//2))
Z2 = list(product([0,1],repeat=N-N//2))

d1 = defaultdict(lambda:5000)
d2 = defaultdict(lambda:5000)

for z in Z1:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[i]
            val_b += b[i]
            cost += c[i]
    if cost < d1[(val_a,val_b)]:
        d1[(val_a,val_b)] = cost

for z in Z2:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[N//2+i]
            val_b += b[N//2+i]
            cost += c[N//2+i]
    if cost < d2[(val_a,val_b)]:
        d2[(val_a,val_b)] = cost

vals = []
now = 1
while True:
    if Ma*now <= sum(a) and Mb*now <= sum(b):
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = 5000
for k in d1.keys():
    for v in vals[::-1]:
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if left_a < 0 or left_b < 0:
            break
        if d1[k]+d2[(left_a,left_b)] < ans:
            ans = d1[k]+d2[(left_a,left_b)]

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

Fixed submission:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                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]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

n = N//2
Z1 = list(product([0,1],repeat=n))
Z2 = list(product([0,1],repeat=N-n))

d1 = defaultdict(list)
d2 = defaultdict(list)

for bit in range(1<<n):
    L = bit.bit_length()
    val_a = 0
    val_b = 0
    cost = 0
    for i in range(L):
        if bit>>i&1:
            val_a += a[n-1-i]
            val_b += b[n-1-i]
            cost += c[n-1-i]
    d1[(val_a,val_b)].append(cost)

for k in d1.keys():
    d1[k].sort()

for bit in range(1<<(N-n)):
    L = bit.bit_length()
    val_a = 0
    val_b = 0
    cost = 0
    for i in range(L):
        if bit>>i&1:
            val_a += a[N-1-i]
            val_b += b[N-1-i]
            cost += c[N-1-i]
    d2[(val_a,val_b)].append(cost)

for k in d2.keys():
    d2[k].sort()

vals = []
now = 1
while True:
    if Ma*now <= sum(a) and Mb*now <= sum(b):
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = float('inf')
for v in vals:
    for k in d1.keys():
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if d2[(left_a,left_b)]:
            if d1[k][0]+d2[(left_a,left_b)][0] < ans:
                ans = d1[k][0]+d2[(left_a,left_b)][0]

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                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]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# Ma:Mbを満たす量を全探索する
# 量を決めたときの最小予算は半分全列挙から分かる

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

Z1 = list(product([0,1],repeat=N//2))
Z2 = list(product([0,1],repeat=N-N//2))

d1 = defaultdict(list)
d2 = defaultdict(list)

for z in Z1:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[i]
            val_b += b[i]
            cost += c[i]
    d1[(val_a,val_b)].append(cost)

for k in d1.keys():
    d1[k].sort()

for z in Z2:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[N//2+i]
            val_b += b[N//2+i]
            cost += c[N//2+i]
    d2[(val_a,val_b)].append(cost)

for k in d2.keys():
    d2[k].sort()

vals = []
now = 1
while True:
    if Ma*now <= sum(a) and Mb*now <= sum(b):
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = float('inf')
for v in vals:
    for k in d1.keys():
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if d2[(left_a,left_b)]:
            if d1[k][0]+d2[(left_a,left_b)][0] < ans:
                ans = d1[k][0]+d2[(left_a,left_b)][0]

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                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]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# Ma:Mbを満たす量を全探索する
# 量を決めたときの最小予算は半分全列挙から分かる

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

Z1 = list(product([0,1],repeat=N//2))
Z2 = list(product([0,1],repeat=N-N//2))

d1 = defaultdict(list)
d2 = defaultdict(list)

for z in Z1:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[i]
            val_b += b[i]
            cost += c[i]
    d1[(val_a,val_b)].append(cost)

for k in d1.keys():
    d1[k].sort()

for z in Z2:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[N//2+i]
            val_b += b[N//2+i]
            cost += c[N//2+i]
    d2[(val_a,val_b)].append(cost)

for k in d2.keys():
    d2[k].sort()

vals = []
now = 1
while True:
    if max(Ma*now,Mb*now) <= 10*N:
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = float('inf')
for v in vals:
    for k in d1.keys():
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if d2[(left_a,left_b)]:
            if d1[k][0]+d2[(left_a,left_b)][0] < ans:
                ans = d1[k][0]+d2[(left_a,left_b)][0]

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                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]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)