Mock CCC '19 Contest 1 S4 - Souma and Food

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Souma Yukihira - Shokugeki no Souma!

Souma wants to make a small amount of a food F.

To make the food F, he needs to prepare a mixture of two ingredients X_1 and X_2, with a ratio of M_{X_1} : M_{X_2}, both mass in grams.

Unfortunately, he has ran out of ingredients at his house. Therefore, he will go to the local grocery store to purchase the needed ingredients.

The grocery store sells N kinds of ingredients. For each ingredient, there is exactly one package of it in stock.

The package of ingredient i contains a_i grams of the ingredient X_{1_i} and b_i grams of the ingredient X_{2_i}, sold for c_i dollars.

Souma intends to purchase some of these packages. He needs to use all of the purchased items to make his food F.

Find the minimum amount of money required for him to make his desired food, F.

If it is impossible to make his desired food, output -1.

Constraints

  • 1 \le N \le 40
  • 1 \le a_i, b_i, M_{X_1}, M_{X_2} \le 10
  • 1 \le c_i \le 100

Input Specification

The first line of input will contain 3 space separated integers, N, M_{X_1}, and M_{X_2}.

The next N lines of input will contain 3 space separated integers, a_i, b_i, and c_i.

Sample Input 1

1 1 10
10 10 10

Sample Output 1

-1

Sample Input 2

3 1 1
1 2 1
2 1 2
3 3 10

Sample Output 2

3

Comments

There are no comments at the moment.