Fișierul intrare/ieșire	rucsac1.in, rucsac1.out	Sursă	Infoarena
Autor	teorie	Adăugată de	Marcela • Marcela
Timp de execuție pe test	0.1 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Rucsac 1

Se dă o mulțime formată din N obiecte, fiecare fiind caracterizat de o greutate și un profit.

Cerință

Să se gasească o submulțime de obiecte astfel încît suma profiturilor lor sa fie maximă, iar suma greutăților lor să nu depașească o valoare G.

Date de intrare

Pe prima linie a fișierului de intrare rucsac1.in se vor gasi valorile N si G, cu semnificația din enunț. Pe următoarele N linii se vor găsi perechile de valori W_i si P_i, reprezentand greutatea, respectiv profitul obiectului i.

Date de ieșire

În fișierul de ieșire rucsac1.out se va afisa o singura valoare P_max, profitul maxim care poate fi obținut respectînd condiția problemei.

Restricții

• 1 ≤ N ≤ 5000
• 1 ≤ G ≤ 10 000
• 1 ≤ W_i, P_i ≤ 10 000

Exemplu

Explicație

Luăm obiectele 1, 2, 4, 5 si 6, a căror greutate este 10, iar suma profiturilor este 29.