Rucsac

rucsac

== include(page="template/taskheader" task_id="rucsac") ==

Se da o multime formata din $N$ obiecte, fiecare fiind caracterizat de o greutate si un profit. Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima, iar suma greutatilor lor sa nu depaseasca o valoare $G$.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie a fişierul $rucsac.in$ se vor gasi valorile $N$ si $G$, cu semnificatia din enunt. Pe urmatoarele $N$ linii se vor gasi perechile de valori $w{~i~}$ si $p{~i~}$, reprezentand greutatea, respectiv profitul obiectului $i$.

Fişierul de intrare $rucsac.in$ ...

h2. Date de ieşire

În fişierul de ieşire $rucsac.out$ se va afisa o singura valoare $P$, profitul maxim care poate fi obtinut respectand conditia problemei.

În fişierul de ieşire $rucsac.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 5000$
* $1 ≤ G ≤ 10000$

* $... ≤ ... ≤ ...$

h2. Exemplu