Vesmírne lode

Predstavte si, že ste hlavným logistikom v Medzihviezdnej Federácii, ktorá plánuje dôležitú expedíciu na vzdialenú planétu. Vašou úlohou je vyslať presne $V$ skúsených veliteľov a $K$ mladých kadetov.

Máte k dispozícii $n$ typov vesmírnych lodí, ktoré sa líšia kapacitou pre každý typ personálu a cenou. Každý typ lode $i$ má špecifikáciu:

• $v_i$: počet veliteľov, ktorých loď pojme.
• $k_i$: počet kadetov, ktorých loď pojme.
• $p_i$: celková cena prenájmu tejto lode v galaktických kreditoch.

Je dôležité, aby:

• Velitelia cestovali len na sedadlách pre veliteľov a kadeti len na sedadlách pre kadetov. Nemôžu si vymieňať miesta.
• Musíte obsadiť presne $V$ veliteľov a $K$ kadetov. Nemôžete poslať viac ani menej ľudí, než je presne požadované, a žiadna časť kapacity lode nesmie zostať nevyužitá (nemožno mať prázdne miesta).

Vašou úlohou je nájsť najlacnejšiu kombináciu lodí, ktorá presne splní požiadavky na počet veliteľov a kadetov. Môžete si byť istí, že vždy existuje spôsob, ako prepraviť všetkých, pretože sú k dispozícii aj lode s kapacitou pre jedného veliteľa alebo jedného kadeta.

Ako by ste navrhli algoritmus, ktorý zabezpečí, že Medzihviezdna Federácia minie čo najmenej kreditov?

Vstup

Na prvom riadku vstupu nájdete 3 čísla $n, V, K$ -- počet dostupných typov lodí, počet veliteľov a počet kadetov.

Nasleduje $n$ riadkov, ktoré obsahujú čísla $v_i, k_i, p_i$ pre každý typ lode.

Výstup

Na jediný riadok výstupu vypíšte jedno číslo -- najmenší počet kreditov, ktoré musí Medzihviezdna Federácia minúť na prepravu všetkého personálu.

Príklad

4 2 3
1 0 100
0 1 80
1 1 150
1 2 200

350