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

numai dacă în momentul când hoţii trec pe uşa dintre camerele i şi i + 1 există cel puţin x{~i~} + 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.

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.

se află numerele v{~i~}, g{~i~}, x{~i~}, separate prin spaţii.

h2. Date de ieşire

h2. Exemplu
|_. hoata.in |_. hoata.out |

|lol|ii|

|
3
2 1 3