CodeEff/ECCO huggingface dataset:
# Original solution
from collections import defaultdict

def dfs(source, sink, flow, connect):
    if source == sink:
        return flow
    used[source] = 1
    for i, (target, cost, rev_i) in enumerate(connect[source]):
        if not used[target] and cost > 0:
            that_flow = dfs(target, sink, min(flow, cost), connect)
            if that_flow > 0:
                connect[source][i][1] -= that_flow
                connect[target][rev_i][1] += that_flow
                return that_flow
    return 0

v_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(e_num):
    s, t, cost = (int(n) for n in input().split(" "))
    connect[s].append([t, cost, len(connect[t])])
    connect[t].append([s, 0, len(connect[s]) - 1])

answer = 0
base_used = [0 for n in range(v_num)]
while True:
    used = base_used.copy()
    now_flow = dfs(0, v_num - 1, float("inf"), connect)
    if now_flow == 0:
        break
    answer += now_flow
print(answer)

# Optimized solution
from collections import defaultdict

def bfs(start, end, connect, v_num, flow):
    level = [-1] * v_num
    level[start] = 0
    queue = [start]
    while queue:
        v = queue.pop()
        for next_v in connect[v]:
            if flow[v][next_v] > 0 and level[next_v] < 0:
                level[next_v] = level[v] + 1
                queue.append(next_v)
    return level

def dfs(here, end, connect, level, flow, minimum_f, visited):
    if here == end:
        return minimum_f
    for next_v in connect[here]:
        if not visited[here][next_v] and flow[here][next_v] > 0 and level[here] < level[next_v]:
            visited[here][next_v] = 1
            temp_f = dfs(next_v, end, connect, level, flow, min(flow[here][next_v], minimum_f), visited)
            if temp_f:
                flow[here][next_v] -= temp_f
                flow[next_v][here] += temp_f
                # print(flow)
                return temp_f
    return 0

v_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
flow = defaultdict(lambda: defaultdict(int))
for _ in range(e_num):
    s, t, c = list(map(int, input().split(" ")))
    connect[s].append(t)
    connect[t].append(s)
    flow[s][t] = c
start = 0
end = v_num - 1
answer = 0
while True:
    level = bfs(start, end, connect, v_num, flow)
    if level[end] < 0:
        print(answer)
        break
    visited = defaultdict(lambda: defaultdict(int))
    temp_f = dfs(start, end, connect, level, flow, float("inf"), visited)
    while temp_f > 0:
        answer += temp_f
        temp_f = dfs(start, end, connect, level, flow, float("inf"), visited)
# Original solution
def main():
    nvertices, nedges = list(map(int, input().split()))
    adj = [[0 for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = list(map(int, input().split()))
        adj[u][v] = c

    INF = float('inf')
    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, adj)
        if parents is None:
            break
        v = nvertices - 1
        f = INF
        while parents[v] != -1:
            f = min(f, adj[parents[v]][v])
            v = parents[v]

        ans += f
        v = nvertices - 1
        while parents[v] != -1:
            adj[parents[v]][v] -= f
            adj[v][parents[v]] += f
            v = parents[v]

    print(ans)


def bfs(s, t, adj):
    visited = [False] * len(adj)
    que = [s]
    parents = [-1] * len(adj)
    while que:
        u = que.pop(0)
        visited[u] = True
        if u == t:
            return parents

        for v in range(len(adj)):
            if not visited[v] and adj[u][v] > 0:
                parents[v] = u
                que.append(v)

    return None


main()

# Optimized solution
def main():
    nvertices, nedges = list(map(int, input().split()))
    adj = [[0] * nvertices for j in range(nvertices)]
    for i in range(nedges):
        u, v, c = list(map(int, input().split()))
        adj[u][v] = c

    INF = float('inf')
    ans = 0
    while True:
        parents = bfs(0, nvertices - 1, adj)
        if parents is None:
            break
        v = nvertices - 1
        f = INF
        while parents[v] != -1:
            f = min(f, adj[parents[v]][v])
            v = parents[v]

        ans += f
        v = nvertices - 1
        while v != 0:
            u = parents[v]
            adj[u][v] -= f
            adj[v][u] += f
            v = u

    print(ans)


def bfs(s, t, adj):
    nvertices = len(adj)
    visited = [False] * nvertices
    visited[0] = True
    que = [s]
    parents = [-1] * nvertices
    while que:
        u = que.pop(0)
        if u == t:
            return parents

        for v in range(len(adj)):
            if not visited[v] and adj[u][v] > 0:
                parents[v] = u
                visited[v] = True
                que.append(v)

    return None


main()
# Original solution
G_MAX = 40*10
N_MAX = 40
INF = float('inf')

dp = [[[INF]*(G_MAX+1) for _ in range(G_MAX+1)] 
      for _ in range(N_MAX+1)]
N,Ma,Mb = list(map(int, input().split()))
a,b,c = [],[],[]
for _ in range(N):
    ai,bi,ci = list(map(int, input().split()))
    a.append(ai)
    b.append(bi)
    c.append(ci)

dp[0][0][0] = 0
from math import isinf
for i in range(N):
    for ca in range(G_MAX+1):
        for cb in range(G_MAX+1):
            if isinf(dp[i][ca][cb]): continue
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb],
                                 dp[i][ca][cb])
            dp[i+1][ca+a[i]][cb+b[i]] = min(dp[i+1][ca+a[i]][cb+b[i]],
                                           dp[i][ca][cb]+c[i])
            
    
ans = INF
for ca in range(1,G_MAX+1):
    for cb in range(1,G_MAX+1):
        if ca*Mb==cb*Ma:
            ans = min(ans, dp[N][ca][cb])
            
if isinf(ans): ans = -1
print(ans)

# Optimized solution
from math import isinf

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

W_MAX = 40*10
dp = [[float('inf')]*(W_MAX+1) for _ in range(W_MAX+1)]
dp[0][0] = 0

for i in range(N):
    for wa in reversed(list(range(W_MAX+1))):
        for wb in reversed(list(range(W_MAX+1))):
            if isinf(dp[wa][wb]): continue
            if wa+a[i]<=W_MAX and wb+b[i]<=W_MAX:
                dp[wa+a[i]][wb+b[i]] = min(dp[wa+a[i]][wb+b[i]],
                                           dp[wa][wb]+c[i])

ans = float('inf')
for wa in range(1, W_MAX+1):
    for wb in range(1, W_MAX+1):
        if wa*Mb == wb*Ma:
            ans = min(ans, dp[wa][wb])

if isinf(ans): ans = -1
print(ans)
# Original solution
N, Ma, Mb = list(map(int, input().split()))

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

M = 401
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  i = M - a - 1
  while i >= 0:
    j = M - b - 1
    while j >= 0:
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
      j -= 1
    i -= 1

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)


# Optimized solution
N, Ma, Mb = list(map(int, input().split()))

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

M = 1 + min(sum([ a for a, b, c in G ]),
            sum([ b for a, b, c in G ]) )
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  i = M - a - 1
  while i >= 0:
    j = M - b - 1
    while j >= 0:
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
      j -= 1
    i -= 1

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)
# Original solution
N, Ma, Mb = list(map(int, input().split()))

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

M = 1 + min(sum([ a for a, b, c in G ]),
            sum([ b for a, b, c in G ]) )
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  i = M - a - 1
  while i >= 0:
    j = M - b - 1
    while j >= 0:
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
      j -= 1
    i -= 1

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)


# Optimized solution
N, Ma, Mb = list(map(int, input().split()))

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

M = 1 + min(sum([ a for a, b, c in G ]),
            sum([ b for a, b, c in G ]) )
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  for i in reversed(list(range(0, M - a))):
    for j in reversed(list(range(0, M - b))):
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)
# Original solution
N, Ma, Mb = list(map(int, input().split()))
D = [tuple(map(int, input().split())) for _ in range(N)]

def dfs(L, D, i, ta, tb, tc):
    if i==len(D):
        key = (ta, tb)
        L[key] = min(L[key], tc) if key in L else tc
        return
    a, b, c = D[i]
    dfs(L, D, i+1, ta  , tb  , tc  )
    dfs(L, D, i+1, ta+a, tb+b, tc+c)

L1, L2 = {}, {}
dfs(L1, D[:N//2], 0, 0, 0, 0)
dfs(L2, D[N//2:], 0, 0, 0, 0)

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))

# Optimized solution
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 list(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))
# Original solution
INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    S2 = []

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        S2.append((A2, B2, C2))

    D = dict()
    S2.sort(key=lambda x: x[2], reverse=True)

    res = INF

    for i in range(2**M):
        a, b, c = S2[i]
        x = Mb * a - Ma * b
        if x == 0 and c > 0:
            res = min(res, c)
        if not x in D or c > 0:
            D[x] = c

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

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

res = solve(N, Ma, Mb, sol)

print((res if res != INF else -1))

# Optimized solution
INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    D = dict()
    res = INF

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        x = Mb * A2 - Ma * B2
        if x == 0 and C2 > 0:
            res = min(res, C2)
        if not x in D or 0 < C2 < D[x]:
            D[x] = C2

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

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

res = solve(N, Ma, Mb, sol)

print((res if res != INF else -1))
# Original solution
import math
nmax = 40
abmax = 10
INF = 10000

#入力
N, Ma, Mb = list(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)

# Optimized solution
import collections
import copy
INF = 10000

#入力
N, Ma, Mb = list(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 list(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 list(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))
# Original solution
N, Ma, Mb = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(N):
    ai, bi, ci = list(map(int, input().split()))
    A.append(ai)
    B.append(bi)
    C.append(ci)

INF = float('inf')
dp = [[[INF]*401 for i in range(401)] for j in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    for a in range(1, 401):
        if A[i-1] > a:
            continue
        for b in range(1, 401):
            if A[i-1] <= a and B[i-1] <= b:
                dp[i][a][b] = min(dp[i-1][a][b], dp[i-1][a-A[i-1]][b-B[i-1]] + C[i-1])

ans = INF
for i in range(1, 401):
    target_a = Ma * i
    target_b = Mb * i
    if target_a > 400 or target_b > 400:
        break
    ans = min(ans, dp[N][target_a-1][target_b-1])

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


# Optimized solution
N, Ma, Mb = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(N):
    ai, bi, ci = list(map(int, input().split()))
    A.append(ai)
    B.append(bi)
    C.append(ci)

INF = float('inf')
dp = [[[INF]*401 for i in range(401)] for j in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(401):
        for b in range(401):
            if dp[i][a][b] == INF:
                continue
            dp[i+1][a][b] = min(dp[i+1][a][b], dp[i][a][b])
            if a + A[i] <= 400 and b + B[i] <= 400:
                dp[i+1][a+A[i]][b+B[i]] = min(dp[i+1][a+A[i]][b+B[i]], dp[i][a][b]+C[i])

ans = INF
for i in range(1, 401):
    target_a = Ma * i
    target_b = Mb * i
    if target_a > 400 or target_b > 400:
        break
    ans = min(ans, dp[N][target_a][target_b])

print((ans if ans != INF else -1))
# Original solution
N, Ma, Mb = list(map(int, input().split()))
Items = [list(map(int, input().split())) for i in range(N)]

# dp[i][a][b] := i個目の薬品までで薬品Aがaグラム、薬品Bがbグラムの混合液を作るために必要な最小予算
dp = [[[float('inf')] * 401 for j in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N):
    ai, bi, ci = Items[i]
    for a in range(401):
        for b in range(401):
            if a + ai <= 400 and b + bi <= 400:
                dp[i + 1][a + ai][b + bi] = min(dp[i][a][b] + ci, dp[i + 1][a + ai][b + bi])
            dp[i + 1][a][b] = min(dp[i][a][b], dp[i + 1][a][b])

ans = float('inf')
i = 1
while Ma * i <= 400 and Mb * i <= 400:
    ans = min(ans, dp[N][Ma * i][Mb * i])
    i += 1

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


# Optimized solution
N, Ma, Mb = list(map(int, input().split()))
Items = [list(map(int, input().split())) for i in range(N)]

# dp[i][a][b] := i個目の薬品までで薬品Aがaグラム、薬品Bがbグラムの混合液を作るために必要な最小予算
dp = [[[float('inf')] * 401 for j in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(1, N + 1):
    ai, bi, ci = Items[i - 1]
    for a in range(401):
        for b in range(401):
            if a - ai >= 0 and b - bi >= 0:
                dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b], dp[i - 1][a - ai][b - bi] + ci)
            else:
                dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])

ans = float('inf')
i = 1
while Ma * i <= 400 and Mb * i <= 400:
    ans = min(ans, dp[N][Ma * i][Mb * i])
    i += 1

print((ans if ans != float('inf') else -1))
# Original solution
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(eval(input()))
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      list(map(int, input().split()))
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,ma,mb = inm()
a = []
b = []
c = []
for i in range(n):
    aa,bb,cc = inm()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp = [[BIG]*(100*n+1) for i in range(100*n+1)]
dp[0][0] = 0
for t in range(n):
    dp2 = [[BIG]*(100*n+1) for i in range(100*n+1)]
    for i in range(10*t+1):
        for j in range(10*t+1):
            if dp[i][j]<BIG:
                dp2[i][j] = min(dp2[i][j],dp[i][j])
                dp2[i+a[t]][j+b[t]] = min( \
                     dp2[i+a[t]][j+b[t]], dp[i][j]+c[t])
    dp = dp2
mn = BIG
for i in range(1,5000):
    if i*max(ma,mb)>n*100:
        break
    #ddprint(f"i {i} n {n} ma {ma} mb {mb} ima {i*ma}")
    mn = min(mn, dp[i*ma][i*mb])
print((-1 if mn==BIG else mn))


# Optimized solution
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(eval(input()))
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      list(map(int, input().split()))
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,ma,mb = inm()
a = []
b = []
c = []
for i in range(n):
    aa,bb,cc = inm()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp = [[BIG]*(10+1) for i in range(10+1)]
dp[0][0] = 0
for t in range(n):
    dp2 = [[BIG]*(10*(t+1)+1) for i in range(10*(t+1)+1)]
    for i in range(10*t+1):
        for j in range(10*t+1):
            if dp[i][j]<BIG:
                dp2[i][j] = min(dp2[i][j],dp[i][j])
                dp2[i+a[t]][j+b[t]] = min( \
                     dp2[i+a[t]][j+b[t]], dp[i][j]+c[t])
    dp = dp2
mn = BIG
for i in range(1,5000):
    if i*max(ma,mb)>n*10:
        break
    #ddprint(f"i {i} n {n} ma {ma} mb {mb} ima {i*ma}")
    mn = min(mn, dp[i*ma][i*mb])
print((-1 if mn==BIG else mn))
# Original solution
def main():
    INF = 10 ** 20
    n, ma, mb = list(map(int, input().split()))
    dp = [[INF] * 401 for _ in range(401)]
    dp[0][0] = 0
    for _ in range(n):
        a, b, c = list(map(int, input().split()))
        for i in range(400 - a, -1, -1):
            for j in range(400 - b, -1, -1):
                dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)
    
    ans = INF
    for i in range(1, 400):
        if ma * i > 400 or mb * i > 400:
            break
        ans = min(ans, dp[ma * i][mb * i])
    if ans >= INF:
        print((-1))
    else:
        print(ans)

main()

# Optimized solution
def main():
    INF = 10 ** 5
    n, ma, mb = list(map(int, input().split()))
    dp = [[INF] * 401 for _ in range(401)]
    dp[0][0] = 0
    for _ in range(n):
        a, b, c = list(map(int, input().split()))
        for i in range(400 - a, -1, -1):
            dpi = dp[i]
            dpia = dp[i + a]
            for j in range(400 - b, -1, -1):
                if dpia[j + b] > dpi[j] + c:
                    dpia[j + b] = dpi[j] + c
    
    ans = INF
    for i in range(1, 400):
        if ma * i > 400 or mb * i > 400:
            break
        ans = min(ans, dp[ma * i][mb * i])
    if ans >= INF:
        print((-1))
    else:
        print(ans)

main()
# Original solution
N,Ma,Mb=list(map(int, input().strip().split()))
abc=[list(map(int, input().strip().split())) for i in range(N)]
maxW=N*10
dp=[[[float("inf")]*(maxW+1) for _ in range(maxW+1)]for __ in range(N+1)]
dp[0][0][0]=0
for i in range(N):
    a,b,c=abc[i]
    for ai  in range(maxW):
        for bi in range(maxW):
            if dp[i][ai][bi]==float("inf"):continue
            dp[i+1][ai][bi] = min(dp[i+1][ai][bi],dp[i][ai][bi])
            dp[i+1][ai+a][bi+b] = min(dp[i][ai][bi]+c,dp[i+1][ai+a][bi+b])
cost=float("inf")
Mad=Ma
Mbd=Mb
while Ma<=maxW and Mb <=maxW:
    cost=min(dp[-1][Ma][Mb],cost)
    Ma+=Mad
    Mb+=Mbd
print((-1 if cost==float("inf") else cost))

# Optimized solution
N,Ma,Mb=list(map(int, input().strip().split()))
abc=[list(map(int, input().strip().split())) for i in range(N)]
maxW=N*10
dp=[{} for __ in range(N+1)]
dp[0][(0,0)]=0
for i in range(N):
    a,b,c=abc[i]
    for k,v in list(dp[i].items()):
        dp[i+1][k]=min(dp[i][k], dp[i+1][k]if k in dp[i+1] else float("inf"))
        dp[i+1][k[0]+a,k[1]+b]=min(dp[i][k]+c, dp[i+1][k[0]+a,k[1]+b] if (k[0]+a,k[1]+b)in dp[i+1] else float("inf"))

cost=float("inf")
Mad=Ma
Mbd=Mb
while Ma<=maxW and Mb <=maxW:
    if (Ma,Mb) in dp[-1]:
        cost=min(dp[-1][Ma,Mb],cost)
    Ma+=Mad
    Mb+=Mbd
print((-1 if cost==float("inf") else cost))
# Original solution
N,Ma,Mb=list(map(int,input().split()))
medic=[tuple(map(int,input().split())) for _ in range(N)]
from collections import defaultdict
inf = float('inf')
dp=defaultdict(lambda :inf)
dp[(0,0)]=0
for n in range(N):
    dpc=dp.copy()
    a,b,c=medic[n]
    for d,cost in list(dpc.items()):
        da,db=d
        dp[(da+a,db+b)]=min(dp[(da+a,db+b)],c+cost)
ans=inf
nowa,nowb=Ma,Mb
while nowa<=400 and nowb<=400:
    ans=min(ans,dp[nowa,nowb])
    nowa+=Ma
    nowb+=Mb
if ans>4000:ans=-1
print(ans)

# Optimized solution
N,Ma,Mb=list(map(int,input().split()))
medic=[tuple(map(int,input().split())) for i in range(N)]
from collections import defaultdict
dp=defaultdict(lambda : float('inf'))
dp[(0,0)]=0
for a,b,c in medic:
    dpc=dp.copy()
    for k,v in list(dpc.items()):
        x,y=k
        dp[(x+a,y+b)]=min(dp[(x+a,y+b)],v+c)
ans=10**10
for i in range(1,1+N):
    ans=min(ans,dp[(Ma*i,Mb*i)])
if ans>10**9:
    print((-1))
else:
    print(ans)