Diners infinits! P12723

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 \le n \le 500$, $2 \le p \le 100$, $1 \le m \le 100$, i $1 \le b_i < a_i \cdot p_i \le p$.

Sortida

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