Se citesc n obiecte, fiecare cu o greutate si o valoare, si capacitatea G a unui rucsac. Fiecare obiect poate fi luat INTREG sau deloc (nu se accepta fractiuni). Determinati, folosind Programarea Dinamica, valoarea maxima ce poate fi transportata fara a depasi capacitatea G.
- Date de intrare
- Pe prima linie se citesc n si G. Urmeaza n linii, fiecare cu doua numere: greutatea si valoarea unui obiect.
- Date de iesire
- Se afiseaza un singur numar: valoarea maxima.
- Restrictii
- 1 <= n <= 500, 1 <= G <= 2000, 1 <= greutate, valoare <= 1000
Exemple
Exemplul 1
Intrare
3 50 10 60 20 100 30 120
Iesire
220
Exemplul 2
Intrare
4 10 5 10 4 40 6 30 3 50
Iesire
90