h2. 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 &le; i &le; N$ se află numerele <tex> ${v}_{i}$, ${g}_{i}$, ${x}_{i}$ </tex> separate prin spaţii.

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

* $1 ≤ $N$ ≤ 300$
* $1 ≤ $K$ ≤ 50$
* $1 ≤ $G$ ≤ 300$

* $1 &le;$ <tex> ${v}_{i}$ </tex> $&le; 300$, oricare ar fi $1 &le; i &le; N$.
* $1 &le;$ <tex> ${g}_{i}$ </tex> $&le; 300$, oricare ar fi $1 &le; i &le; N$.
* $1 &le;$ <tex> ${x}_{i}$ </tex> $&le; 50$, oricare ar fi $1 &le; i &le; N$.
* $1 &le;$ <tex> ${S}_{N}$ </tex> $&le; 900$, unde cu <tex> ${S}_{N}$ </tex> am notat suma valorilor $N$ corespunzătoare celor $T$ scenarii.

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

|_. # |_. Punctaj |_. Restricţii |
| $1$

$18$
$40$
$31$

| $N &le; 4, K &le; 3, G &le; 7$, <tex> ${S}_{N}$ </tex> $&le;$ $12$, <tex> ${v}_{i}$ </tex> $&le;$ $20$, $2$ $&le;$ <tex> ${g}_{i}$ </tex> $&le;$ $7$, <tex> ${x}_{i}$ </tex> $&le;$ $3$, oricare ar fi $1 &le; i &le; N$.
Există $1 &le; j &le; N$ astfel încât <tex> ${x}_{i}$ </tex> $=$ $K$ oricare ar fi $1 &le; i &le; N$, $i$ &ne; $j$.
$N &le; 40, G &le; 40$, <tex> ${S}_{N}$ </tex> $&le;$ $120$, <tex> ${v}_{i}$ </tex> $&le;$ $40$, <tex> ${g}_{i}$ </tex> $&le;$ $40$, oricare ar fi $1 &le; i &le; N$.

| $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$.
Există $1 ≤ j ≤ N$ astfel încât $x{~i~} = K$ oricare ar fi $1 ≤ i ≤ N$, $i$ ≠ $j$.
$N ≤ 40, G ≤ 40, S{~N~} ≤ 120, v{~i~} ≤ 40, g{~i~} ≤ 40$, oricare ar fi $1 ≤ i ≤ N$.

Fără restricţii suplimentare.
|

**Primul scenariu**

Avem $N = 2$ camere şi $K = 1$ hoţ înzestrat cu un rucsac de capacitate $G = 3$. În camera $1$ se află 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 <tex> ${x}_{1}$ </tex> = $1$, iar alarma dintre camera $2$ şi ieşire are <tex> ${x}_{1}$ </tex> = $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$.

Avem $N = 2$ camere şi $K = 1$ hoţ înzestrat cu un rucsac de capacitate $G = 3$. În camera $1$ se află 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**