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

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.

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

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

* Pentru a primi punctajul pentru aceasta problema diferenta in modul dintre solutiile voastre si ale comisiei trebuie sa fie mai mica decat $10^-6^$

h2. Exemplu

10 10 0
10 10 0
5 7 1

| This is another
  text written on
  multiple lines.

| 13.571428

|
h3. Explicaţie

...

Deoarece nu vom putea lua primele $2$ obiecte pentru ca sunt prea grele, vom lua unul dintre ele, iar pe al treilea il vom partitiona in doua obiecte astfel incat cu unul din cele doua sa umplem ghiozdanul.

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