Diferențe pentru problema/rucsac1 între reviziile #5 si #9

h2. 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.

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 W[~i~] si P[~i~], 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 P[~max~], profitul maxim care poate fi obținut respectînd 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 ≤ W[~i~], P[~i~] ≤ 10 000$

* $1 ≤ _N_ ≤ 5000$
* $1 ≤ _G_ ≤ 10 000$
* $1 ≤ _W[~i~]_, _P[~i~]_ ≤ 10 000$

h2. Exemplu