Diners infinits! P12723

Statement

thehtml

L’Izan ha descobert una forma de fer-se ric! (O això diu.) S’ha adonat que, si es compren certs productes en packs grans, són més barats. Llavors, si compra packs grans i després els revèn d’un en un…

L’Izan ha trobat n productes on pot aplicar la seva técnica. Per a l’i-èsim producte, el preu d’una unitat és de p_i euros. Però en pot comprar a_i unitats per només b_i euros!

Al principi, l’Izan té p euros que pot usar per comprar packs, que al final vendrà per separat. A més, només pot comprar en total m packs de productes de qualsevol mena. Quin és el màxim benefici que pot aconseguir?

Entrada

L’entrada consisteix en diversos casos, només amb nombres naturals. Cada cas comença amb n, p i m. Segueixen n triples p_i a_i b_i que descriuen cada producte. Podeu suposar 1 ≤ n ≤ 500, 2 ≤ p ≤ 100, 1 ≤ m ≤ 100, i 1 ≤ b_i < a_i · p_i ≤ p.

Sortida

Per a cada cas, escriviu el màxim benefici possible.

Public test cases

Input

2 100 1
10 3 21
20 5 85

2 100 2
10 3 21
20 5 85

2 1000 2
10 3 21
20 5 85

5 1115 4
250 4 500
3 40 100
11 1 10
300 3 899
1 1115 1114

Output

Information

Author: Edgar Moreno
Language: Catalan
Official solutions: C++
User solutions: C++