Under construction

Still being built. Things may change

Vitamins

Interview

Time limit2sMemory limit1024 MB

Summary
Given N tablets with their vitamin C, vitamin D, and price, find the minimum cost to get at least C mg of vitamin C and D mg of vitamin D.
Level

Medium5 of 10

Topics
Dynamic programming
Solved
No attempts yet

Problem

Winter is a season when it is important to get enough vitamins. Adomas knows this and walks into the pharmacy Vitaminų Pasaulis, which sells many kinds of multivitamin tablets. Taking too many vitamins can be harmful, so the pharmacy sells at most one tablet of each kind to a single customer.

Adomas is most interested in vitamin C, which strengthens the immune system, and vitamin D, which is essential for bones and teeth. The shop has so many different tablets that Adomas gets confused.

The amount of vitamin C and vitamin D in each tablet is known, and so is the price of each tablet. Find the minimum amount Adomas must pay to buy at least CC milligrams of vitamin C and at least DD milligrams of vitamin D.

Input

The first line contains three integers: the number of tablets NN, and the amounts CC and DD that Adomas wants.

Each of the next NN lines describes one tablet. It contains the amount of vitamin C cic_i, the amount of vitamin D did_i (in milligrams), and the price of the tablet kik_i (in cents). All numbers are integers.

Output

Print one integer: the minimum number of cents Adomas must spend to buy at least CC milligrams of vitamin C and at least DD milligrams of vitamin D.

A solution always exists, because buying all the tablets gives Adomas at least the required amounts.

Constraints

  • 1≤N≤1001 \le N \le 100
  • 0≤ci,C≤10 0000 \le c_i, C \le 10\,000
  • 0≤di,D≤5000 \le d_i, D \le 500
  • 1≤ki≤10001 \le k_i \le 1000

Examples1

  1. Example 1

    Input
    5 300 50
100 30 50
200 10 25
100 50 100
400 0 80
0 100 200
    Expected output
    125