Diners infinits! P12723


Statement
 

pdf   zip

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 pi euros. Però en pot comprar ai unitats per només bi 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 pi ai bi que descriuen cada producte. Podeu suposar 1 ≤ n ≤ 500, 2 ≤ p ≤ 100, 1 ≤ m ≤ 100, i 1 ≤ bi < ai · pip.

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

    15
    18
    30
    1021
    
  • Information
    Author
    Edgar Moreno
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++