Se citesc n obiecte, fiecare cu o greutate si o valoare, si capacitatea G a unui rucsac. Determinati, folosind Programarea Dinamica, un subset de obiecte (fiecare luat intreg sau deloc) de valoare totala maxima, cu greutatea totala cel mult G, si afisati indicii obiectelor alese.
- Date de intrare
- Pe prima linie se citesc n si G. Urmeaza n linii, fiecare cu doua numere: greutatea si valoarea obiectului cu indicele respectiv.
- Date de iesire
- Pe prima linie se afiseaza valoarea maxima. Pe a doua linie se afiseaza indicii (numerotati de la 1) obiectelor alese, in ordine crescatoare, separati prin spatiu.
- 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 2 3
Exemplul 2
Intrare
4 10 5 10 4 40 6 30 3 50
Iesire
90 2 4