== include(page="template/taskheader" task_id="hoata") ==
Î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 rezerva 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

1 ≤ i ≤ N se găseşte o rezerva 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.

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

este instalată între camerele i şi i + 1 şi este caracterizată de o valoare x{~i~}. 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

h2. Date de intrare

Fişierul de intrare $hoata.in$ ...

Prima linie conţine un singur număr natural T, reprezentând numărul de scenarii. Urmează descrierile
celor T scenarii. Descrierea unui scenariu se face după cum urmează: pe prima linie trei numere naturale
N, K, G, separate prin spaţii; pe următoarele N linii câte trei numere naturale, unde pe linia 1 ≤ i ≤ N
se află numerele v {~i~}, g {~i~}, x {~i~}, separate prin spaţii.

h2. Date de ieşire

În fişierul de ieşire $hoata.out$ ...

Se vor afişa T linii, reprezentând, în ordinea dată, răspunsurile pentru cele T scenarii date la intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

|#|Punctaj|Restricţii|
|1|11|N ≤ 4, K ≤ 3, G ≤ 7, S{~N~} ≤ 12, v{~i~} ≤ 20, 2 ≤ g{~i~} ≤ 7, x{~i~} ≤ 3, oricare ar fi 1 ≤ i ≤ N.|

h2. Exemplu