Fişierul intrare/ieşire:	ruksak.in, ruksak.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 16
Autor	Florin Chirica	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.25 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	2/5

Vezi solutiile trimise | Statistici

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.

Date de intrare

Pe prima linie a fişierului ruksak.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.

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.

Restricţii

• 1 <= N <= 3 * 10⁵
• 1 <= G <= 3000
• 0 <= W_i, P_i <= 3000
• Multumiri speciale lui Vlad Gavrila pentru enuntul problemei rucsac, caruia i-am dat copy-paste aici. Te pupam si te iubim, cel mai dulce baiat :*

Exemplu
table(example). |_. ruksak.in |_. ruksak.out |
| 6 10
3 7
3 4
1 2
1 9
2 4
1 5
| 29
|

Explicaţie

Luam obiectele 1, 2, 4, 5 si 6, a caror greutate este 10, iar suma profiturilor este 29.

Cum se trimit solutii?