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

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1 &le; i &le; N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare <tex> {v}_{i} </tex> şi greutate <tex> {g}_{i} </tex>. Î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.

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1 &le; i &le; N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare $<tex> {v}_{i} </tex>$ şi greutate <tex> {g}_{i} </tex>. Î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