== include(page="template/taskheader" task_id="bani") ==

Poveste şi cerinţă...

Un tip serios vrea sa faca multi bani. Asa ca el merge in piata cu $N$ obiecte pentru care le stie $valoarea$, $greutatea$ si $daca acestea pot fi partitionate sau nu$. Daca un obiect $i$ are valoarea $val[i]$ si greutatea $greu[i]$ si acesta poate fi partitionat, atunci el se poate partitiona in $2$ obiecte distincte astfel incat $val1[i] + val2[i] = val[i]$ si $greu1[i] + greu2[i] = greu[i]$ si $val1[i] / val[i] = greu1[i] / greu[i]$ unde $greu1[i] si val1[i]$ sunt greutatea si valoarea primului din cele doua obiecte obtinute prin partitionare, iar $greu2[i] si val2[i]$ sunt greutatea si valoarea celui de-al doilea. Stiind ca el are un ghiozdan in care poate cara maxim $G$ unitati, voi trebuie sa calculati valoarea maxima pe care o poate castiga tipul.

h2. Date de intrare

Fişierul de intrare $bani.in$ ...

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

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, G ≤ 750$
* 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 alea comisiei nu trebuie sa depaseasca $10^-6^$

h2. Exemplu
table(example). |_. bani.in |_. bani.out |

| This is some
  text written on
  multiple lines.

| 1
3 15
10 10 0
10 10 0
5 7 1

| This is another
  text written on
  multiple lines.