Se citesc n obiecte, fiecare cu o greutate, un volum si o valoare, si o capacitate maxima de greutate G si un volum maxim disponibil V ale unui rucsac. Fiecare obiect poate fi luat intreg sau deloc. Determinati, folosind Programarea Dinamica, valoarea maxima ce poate fi transportata fara a depasi NICIUNA dintre cele doua limite (greutate si volum).
- Date de intrare
- Pe prima linie se citesc n, G si V. Urmeaza n linii, fiecare cu trei numere: greutatea, volumul si valoarea unui obiect.
- Date de iesire
- Se afiseaza un singur numar: valoarea maxima.
- Restrictii
- 1 <= n <= 100, 1 <= G, V <= 100, 1 <= greutate, volum, valoare <= 1000
Exemple
Exemplul 1
Intrare
3 10 10 2 3 10 3 4 20 4 5 30
Iesire
50
Exemplul 2
Intrare
2 5 5 1 1 5 5 5 6
Iesire
6