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

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 ruksak.in se vor gasi valorile N si G, cu semnificatia din enunt. Pe urmatoarele N linii se vor gasi perechile de valori Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.

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

h2. Date de ieşire

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

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

h2. Restricţii

* 1 <= N <= 10^6
* 1 <= G <= 2000
* 0 <= Wi, Pi <= 2000

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

h2. Exemplu