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

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.

h2. Date de ieşire

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

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

h2. Restricţii

* $1 ≤ N, G ≤ 750$

* $T = 10$
* $1 ≤ N ≤ 750$
* $1 ≤ G ≤ 1000$
* $0 ≤ greu[i] ≤ 1000$ pentru $1 ≤ i ≤ N$
* $1 ≤ val[i] ≤ 5000$ pentru $1 ≤ i ≤ N$

* Daca un obiect $i$ poate fi partitionat atunci $part[i] = 1$, alftel $part[i] = 0$.
* Pentru a primi punctajul pentru aceasta problema diferenta in modul dintre solutiile voastre si ale comisiei trebuie sa fie mai mica decat $10^-6^$, iar comisia va sugereaza sa folositi 8 zecimale la afisare.

9830