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.

Odată ieşiţi din muzeu, hoţii calculează captura totală ca fiind suma valorilor v corespunzătoare lingourilor din cele $K$ rucsacuri. Se dau $T$ scenarii, şi pentru fiecare se cere captura maximă posibilă în condiţiile date, sau $−1$ dacă orice s-ar întâmpla hoţii ar fi prinşi.
 

h2. Date de intrare
Fişierul de intrare $hoata2.in$ ...