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

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.

Date de intrare

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.

Date de ieșire

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

Restricţii

• 1 ≤ T ≤ 900
• 1 ≤ N ≤ 300
• 1 ≤ K ≤ 50
• 1 ≤ G ≤ 300
• $1 ≤ v_i ≤ 300$, oricare ar fi 1 ≤ i ≤ N.
• $1 ≤ g_i ≤ 300$, oricare ar fi 1 ≤ i ≤ N.
• $1 ≤ x_i ≤ 50$, oricare ar fi 1 ≤ i ≤ N.
• $1 ≤ S_N ≤ 900$, unde cu $S_N$ am notat suma valorilor N corespunzătoare celor T scenarii.

Subtask 1 (11 puncte)

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

Subtask 2 (18 puncte)

• Există 1 ≤ j ≤ N astfel încât $x_i = K$ oricare ar fi 1 ≤ i ≤ N, i ̸= j.

Subtask 3 (40 puncte)

• N ≤ 40, G ≤ 40, $S_N ≤ 120, v_i ≤ 40, g_i ≤ 40$, oricare ar fi 1 ≤ i ≤ N.

Subtask 4 (31 puncte)

• Fără restricții suplimentare.

Exemple

stdin

3
2 1 3
10 2 1
9 1 2
2 2 3
10 2 1
9 1 2
2 3 3
10 2 1
9 1 2

stdout

27
46
-1

Explicații

Sunt T = 3 scenarii.

Primul scenariu

Avem N = 2 camere și K = 1 hoț înzestrat cu un rucsac de capacitate G = 3. În camera 1 se afla o rezervă infinită de lingouri de aur de valoare 10 și greutate 2, iar în camera 2 se află o rezervă infinită de lingouri de aur de valoare 9 și greutate 1. Alarma dintre camera 1 și camera 2 are $x_1 = 1$, iar alarma dintre camera 2 și ieșire are $x_2 = 2$. În condițiile date alarmele nu vor suna indiferent ce alege să facă hoțul, așa că acesta poate obține o captura maximă de 27 = 9 + 9 + 9 furând trei lingouri din camera 2.

Al doilea scenariu

Acest scenariu este identic cu primul, doar că avem K = 2 hoți, fiecare având cate un rucsac de capacitate 3. Dacă ambii hoți iau câte 3 lingouri din camera 2, atunci aceștia ar avea o captură totală de 54 = 6 × 9. Din păcate, dacă ar face acest lucru, ei ar fi prinși de alarma dintre camerele 1 și 2. Observăm că ei ar fi prinși de aceasta alarmă chiar și dacă aleg sa nu fure nimic din nicio cameră! Captura maximă, de fapt, se obține, de exemplu, dacă primul hoț alege să fure câte un lingou din fiecare cameră (total 19 = 10 + 9), iar al doilea hoț alege să fure trei lingouri din camera 2 (total 27 = 9 + 9 + 9). În total 46 = 19 + 27.

Al treilea scenariu

Acest scenariu este identic cu primele două, doar că avem K = 3 hoți. În acest caz cei trei hoți nu vor putea trece de camera 1 fără sa declanșeze alarma, deci răspunsul este −1.