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

Poveste şi cerinţă...

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1$ ≤ i ≤ $N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare $v_{i}$ şi greutate $g_{i}$. În prima cameră intră $K$ hoţi, fiecare având în spinare câte un rucsac de capacitate $G$, iniţial gol. Când un hoţ se află în camera $i$, acesta poate sustrage oricâte lingouri din camera curentă şi să le adauge în rucsacul său, cu condiţia ca suma greutăţilor lingourilor din rucsac să nu depăşească $G$. Un lingou o dată furat, acesta va rămâne în rucsacul hoţului până la ieşirea din muzeu.

h2. Date de intrare