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

Hoţii acţionează în grup, aşa că ei vor face turul muzeului în $N$ paşi, după cum urmează: la pasul $1 ≤ i ≤ N$ toţi hoţii avansează din camera $i$ în camera $i + 1$, unde camera $N + 1$ se consideră exteriorul muzeului. Observăm că după primii $i$ paşi toţi hoţii se vor afla în camera $i + 1$. Conducerea muzeului a instalat alarme în dreptul uşilor dintre oricare două camere consecutive. Mai exact, alarma $1 ≤ i ≤ N$ este instalată între camerele $i$ şi $i + 1$ şi este caracterizată de o valoare xi. Aceasta se declanşează dacă şi numai dacă în momentul când hoţii trec pe uşa dintre camerele $i$ şi $i + 1$ există cel puţin $xi + 1$ hoţi ale căror rucsacuri au aceeaşi greutate totală la acel moment, deoarece în acest caz s-ar efectua un control de rutină şi hoţii ar fi prinşi (acest lucru se întâmplă chiar şi dacă hoţii nu au furat nimic până la acel moment). Bineînţeles, alarma $N$ este instalată între camera $N$ şi exteriorul muzeului.

Hoţii acţionează în grup, aşa că ei vor face turul muzeului în $N$ paşi, după cum urmează: la pasul $1 &le; i &le; N$ toţi hoţii avansează din camera $i$ în camera $i + 1$, unde camera $N + 1$ se consideră exteriorul muzeului. Observăm că după primii $i$ paşi toţi hoţii se vor afla în camera $i + 1$. Conducerea muzeului a instalat alarme în dreptul uşilor dintre oricare două camere consecutive. Mai exact, alarma $1 &le; i &le; N$ este instalată între camerele $i$ şi $i + 1$ şi este caracterizată de o valoare <tex> ${x}_{i}$ </tex>. Aceasta se declanşează dacă şi numai dacă în momentul când hoţii trec pe uşa dintre camerele $i$ şi $i + 1$ există cel puţin <tex> ${x}_{i} + 1$ </tex> hoţi ale căror rucsacuri au aceeaşi greutate totală la acel moment, deoarece în acest caz s-ar efectua un control de rutină şi hoţii ar fi prinşi (acest lucru se întâmplă chiar şi dacă hoţii nu au furat nimic până la acel moment). Bineînţeles, alarma $N$ este instalată între camera $N$ şi exteriorul muzeului.

h2. Date de intrare