== include(page="template/taskheader" task_id="rucsac1") ==
Se dă o mulțime formată din N obiecte, fiecare fiind caracterizat de o greutate și un profit.
Se dă o mulțime formată din _N_ obiecte, fiecare fiind caracterizat de o greutate și un profit.
h2. Cerință
Să se gasească o submulțime de obiecte astfel incat suma profiturilor lor sa fie maximă, iar suma greutăților lor să nu depașească o valoare G.
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_.
h2. 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 Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.
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_.
h2. Date de ieșire
În fișierul de ieșire $rucsac1.out$ se va afisa o singura valoare Pmax, profitul maxim care poate fi obținut respectand condiția problemei.
Î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.
h2. Restricții
* $1 ≤ N ≤ 5000$
* $1 ≤ G ≤ 10 000$
* $0 ≤ Wi, Pi ≤ 10 000$
* $1 ≤ _N_ ≤ 5000$
* $1 ≤ _G_ ≤ 10 000$
* $1 ≤ _W[~i~]_, _P[~i~]_ ≤ 10 000$
h2. Exemplu
