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

Poveste şi cerinţă...

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.

h2. Date de intrare

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

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.

h2. Date de ieşire

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

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

h2. Restricţii

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

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

h2. Exemplu