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

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

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$ se va afisa o singura valoare $P{~max~}$, profitul maxim care poate fi obtinut respectand conditia problemei.

h2. Restricţii