h2. Date de intrare

Fişierul de intrare $bani.in$ contine pe prima linie un numar $T$ reprezentand numarul de teste. Pentru fiecare test, pe prima linie se afla doua numere $N$ si $G$ reprezentand numarul de obiecte si respectiv greutatea maxima a ghiozdanului. Pe urmatoarele $N$ linii se afla cate 3 numere $val[i]$, $greu[i]$ si $part[i]$ reprezentand valoarea obiectului $i$, greutatea lui precum si daca acesta poate fi partitionat sau nu.

Fişierul de intrare $bani.in$ contine pe prima linie un numar $T$ reprezentand numarul de teste. Pentru fiecare test, pe prima linie se afla doua numere $N$ si $G$ reprezentand numarul de obiecte si respectiv grutatea maxima a ghiozdanului. Pe urmatoarele $N$ linii se afla cate 3 numere $val[i]$, $greu[i]$ si $part[i]$ reprezentand valoarea obiectului $i$, greutatea lui precum si daca acesta poate fi partitionat sau nu.

h2. Date de ieşire

În fişierul de ieşire $bani.out$ se vor afisa $T$ numere, cate unul pe linie, fiecare reprezentand raspunsul pentru cele $T$ teste.

În fişierul de ieşire $bani.out$ se vor afisa $T$ numere, fiecare reprezentand raspunsul pentru cele $T$ teste.

h2. Restricţii

9830