import sys

from collections import deque

import copy





def get_read_func(fileobject):

    if fileobject == None :

        return raw_input

    else:

        return fileobject.readline



def bfs(X, Ma, Mb):

    #node_list = deque([0, 1])

    drug_dict = {}

    drug_dict[(0, 0)] = 0

    drug_dict[(X[0][0], X[0][1])] = X[0][2]

##    drug_dict[0] = ((0, 0) ,0)

##    drug_dict[1] = ((X[0][0], X[0][1]), X[0][2])

##    depth = 1

    min_cost = sys.maxsize

    new_drug_dict = copy.deepcopy(drug_dict)

    for i in range(1, len(X)):

        for drug in drug_dict:

            cost = drug_dict[drug]

            new_drug = (drug[0] + X[i][0], drug[1] + X[i][1])

            if new_drug not in drug_dict:

                new_drug_dict[new_drug] = cost + X[i][2]

            else:

                new_drug_dict[new_drug] = min(drug_dict[new_drug], cost + X[i][2])

            if new_drug[1] * Ma == new_drug[0] * Mb:

                if new_drug_dict[new_drug] < min_cost:

                    min_cost = new_drug_dict[new_drug]

        drug_dict = copy.deepcopy(new_drug_dict)

    return min_cost





def main():

    if len(sys.argv) > 1:

        f = open(sys.argv[1])

    else:

        f = None

    read_func = get_read_func(f);

    input_raw = read_func().strip().split()

    [N, Ma, Mb] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]

    X = []

    for i in range(N):

        input_raw = read_func().strip().split()

        [a, b, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]

        X.append((a, b, c))



    cost = bfs(X, Ma, Mb)

    if cost < sys.maxsize:

        print(cost)

    else:

        print(-1)





if __name__ == '__main__':

    main()
import sys

from collections import deque

import copy





def get_read_func(fileobject):

    if fileobject == None :

        return raw_input

    else:

        return fileobject.readline



def bfs(X, Ma, Mb):

    #node_list = deque([0, 1])

    drug_dict = {}

    drug_dict[(0, 0)] = 0

    drug_dict[(X[0][0], X[0][1])] = X[0][2]

##    drug_dict[0] = ((0, 0) ,0)

##    drug_dict[1] = ((X[0][0], X[0][1]), X[0][2])

##    depth = 1

    min_cost = sys.maxsize

    new_drug_dict = copy.deepcopy(drug_dict)

    for i in range(1, len(X)):

        for drug in drug_dict:

            cost = drug_dict[drug]

            new_drug = (drug[0] + X[i][0], drug[1] + X[i][1])

            if new_drug not in drug_dict:

                new_drug_dict[new_drug] = cost + X[i][2]

            else:

                new_drug_dict[new_drug] = min(drug_dict[new_drug], cost + X[i][2])

            if new_drug[1] * Ma == new_drug[0] * Mb:

                if new_drug_dict[new_drug] < min_cost:

                    min_cost = new_drug_dict[new_drug]

        drug_dict = copy.deepcopy(new_drug_dict)

    return min_cost



def dp_search(X, Ma, Mb, AMax, BMax):

    dp = [[sys.maxsize for i in range(AMax + 1)] for j in range(BMax + 1)]

    dp[0][0] = 0



    for i in range(len(X)):

        for a in range(AMax, -1, -1):

            for b in range(BMax, -1, -1):

                if dp[a][b] >= sys.maxsize:

                    continue;

                if a + X[i][0] <= AMax and b + X[i][1] <= BMax:

                    dp[a + X[i][0]][b + X[i][1]] = min(dp[a + X[i][0]][b + X[i][1]], dp[a][b] + X[i][2])

    min_cost = sys.maxsize

    for a in range(0 , AMax):

        for b in range(0, BMax):

            if a * Mb == b * Ma and a != 0 and b != 0:

                if dp[a][b] < min_cost:

                    min_cost = dp[a][b]

    return min_cost





def main():

    if len(sys.argv) > 1:

        f = open(sys.argv[1])

    else:

        f = None

    read_func = get_read_func(f);

    input_raw = read_func().strip().split()

    [N, Ma, Mb] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]

    X = []

    for i in range(N):

        input_raw = read_func().strip().split()

        [a, b, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]

        X.append((a, b, c))



    #cost = bfs(X, Ma, Mb)

    cost = dp_search(X, Ma, Mb, N * 10, N * 10)

    if cost < sys.maxsize:

        print(cost)

    else:

        print(-1)





if __name__ == '__main__':

    main()
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None:
        return raw_input
    else:
        return fileobject.readline


def bfs(X, Ma, Mb):
    # node_list = deque([0, 1])
    drug_dict = {}
    drug_dict[(0, 0)] = 0
    drug_dict[(X[0][0], X[0][1])] = X[0][2]
    ##    drug_dict[0] = ((0, 0) ,0)
    ##    drug_dict[1] = ((X[0][0], X[0][1]), X[0][2])
    ##    depth = 1
    min_cost = sys.maxsize
    new_drug_dict = copy.deepcopy(drug_dict)
    for i in range(1, len(X)):
        for drug in drug_dict:
            cost = drug_dict[drug]
            new_drug = (drug[0] + X[i][0], drug[1] + X[i][1])
            if new_drug not in drug_dict:
                new_drug_dict[new_drug] = cost + X[i][2]
            else:
                new_drug_dict[new_drug] = min(drug_dict[new_drug], cost + X[i][2])
            if new_drug[1] * Ma == new_drug[0] * Mb:
                if new_drug_dict[new_drug] < min_cost:
                    min_cost = new_drug_dict[new_drug]
        drug_dict = copy.deepcopy(new_drug_dict)
    return min_cost


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f)
    input_raw = read_func().strip().split()
    [N, Ma, Mb] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    X = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [a, b, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        X.append((a, b, c))
    cost = bfs(X, Ma, Mb)
    if cost < sys.maxsize:
        print(cost)
    else:
        print(-1)


if __name__ == "__main__":
    main()

import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None:
        return raw_input
    else:
        return fileobject.readline


def bfs(X, Ma, Mb):
    # node_list = deque([0, 1])
    drug_dict = {}
    drug_dict[(0, 0)] = 0
    drug_dict[(X[0][0], X[0][1])] = X[0][2]
    ##    drug_dict[0] = ((0, 0) ,0)
    ##    drug_dict[1] = ((X[0][0], X[0][1]), X[0][2])
    ##    depth = 1
    min_cost = sys.maxsize
    new_drug_dict = copy.deepcopy(drug_dict)
    for i in range(1, len(X)):
        for drug in drug_dict:
            cost = drug_dict[drug]
            new_drug = (drug[0] + X[i][0], drug[1] + X[i][1])
            if new_drug not in drug_dict:
                new_drug_dict[new_drug] = cost + X[i][2]
            else:
                new_drug_dict[new_drug] = min(drug_dict[new_drug], cost + X[i][2])
            if new_drug[1] * Ma == new_drug[0] * Mb:
                if new_drug_dict[new_drug] < min_cost:
                    min_cost = new_drug_dict[new_drug]
        drug_dict = copy.deepcopy(new_drug_dict)
    return min_cost


def dp_search(X, Ma, Mb, AMax, BMax):
    dp = [[sys.maxsize for i in range(AMax + 1)] for j in range(BMax + 1)]
    dp[0][0] = 0
    for i in range(len(X)):
        for a in range(AMax, -1, -1):
            for b in range(BMax, -1, -1):
                if dp[a][b] >= sys.maxsize:
                    continue
                if a + X[i][0] <= AMax and b + X[i][1] <= BMax:
                    dp[a + X[i][0]][b + X[i][1]] = min(
                        dp[a + X[i][0]][b + X[i][1]], dp[a][b] + X[i][2]
                    )
    min_cost = sys.maxsize
    for a in range(0, AMax):
        for b in range(0, BMax):
            if a * Mb == b * Ma and a != 0 and b != 0:
                if dp[a][b] < min_cost:
                    min_cost = dp[a][b]
    return min_cost


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f)
    input_raw = read_func().strip().split()
    [N, Ma, Mb] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    X = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [a, b, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        X.append((a, b, c))
    # cost = bfs(X, Ma, Mb)
    cost = dp_search(X, Ma, Mb, N * 10, N * 10)
    if cost < sys.maxsize:
        print(cost)
    else:
        print(-1)


if __name__ == "__main__":
    main()

+def dp_search(X, Ma, Mb, AMax, BMax): +    dp = [[sys.maxsize for i in range(AMax + 1)] for j in range(BMax + 1)] +    dp[0][0] = 0 +    for i in range(len(X)): +        for a in range(AMax, -1, -1): +            for b in range(BMax, -1, -1): +                if dp[a][b] >= sys.maxsize: +                    continue +                if a + X[i][0] <= AMax and b + X[i][1] <= BMax: +                    dp[a + X[i][0]][b + X[i][1]] = min( +                        dp[a + X[i][0]][b + X[i][1]], dp[a][b] + X[i][2] +                    ) +    min_cost = sys.maxsize +    for a in range(0, AMax): +        for b in range(0, BMax): +            if a * Mb == b * Ma and a != 0 and b != 0: +                if dp[a][b] < min_cost: +                    min_cost = dp[a][b] +    return min_cost + + -    cost = bfs(X, Ma, Mb) +    # cost = bfs(X, Ma, Mb) +    cost = dp_search(X, Ma, Mb, N * 10, N * 10)