Se citesc n tipuri de obiecte, fiecare cu o greutate si o valoare, disponibile in cantitate NELIMITATA, si capacitatea G a unui rucsac. Determinati, folosind Programarea Dinamica, valoarea maxima ce poate fi transportata fara a depasi capacitatea G, un tip de obiect putand fi folosit de oricate ori.
- Date de intrare
- Pe prima linie se citesc n si G. Urmeaza n linii, fiecare cu doua numere: greutatea si valoarea unui tip de 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 10 5 10 4 40 6 30
Iesire
80
Exemplul 2
Intrare
2 8 1 1 3 4
Iesire
10