h2. Cerinta

Dandu-se $T$ astfel de scenarii, si pentru fiecare numarul $N$ de gandaci, si sirul $P$, unde al $i$-lea element reprezinta probabilitatea de-a strivi al $i$-lea gandac dintr-o lovitura, calculeaza expectedul de cati gandaci poti strivi daca arunci in mod optim papucii.

Dandu-se numarul $N$ de gandaci, si sirul $P$, unde al $i$-lea element reprezinta probabilitatea de-a strivi al $i$-lea gandac dintr-o lovitura, calculeaza expectedul de cati gandaci poti strivi daca arunci in mod optim papucii.

h2. Date de intrare
Datele de intrare se citesc din fisierul $blindpunch.in$.

Prima linie contine numarul $T$, reprezentand numarul de teste.
 
Prima linie a fiecarui test contine numerele $N$ si $K$, reprezentand numarul de gandaci si respectiv numarul de papuci la dispozitie.

Prima linie contine numerele $N$ si $K$, reprezentand numarul de gandaci si respectiv numarul de papuci la dispozitie.

Urmatoarea linie contine sirul $P$ de lungime $N$.

Datele de iesire se afiseaza in fisierul $blindpunch.out$.

Afisati $T$ linii, pe linia $i$ fiind expectedul numarului total de gandaci striviti daca aruncati in mod optim papucii in al $i$-lea scenariu.

Afisati expectedul numarului total de gandaci striviti daca aruncati in mod optim papucii.

h2. Restricţii

* $1 ≤ N, K, T ≤ 10^6^$

* $1 ≤ N, K ≤ 10^6^$

* $0 ≤ P~i~ ≤ 1$

* Pentru teste in valoare de $40$ de puncte, se garanteaza ca $1 ≤ N, K, T ≤ 500$.
* Pentru alte teste in valoare de $40$ de puncte, se garanteaza ca $1 ≤ N, K, T ≤ 5000$.

* Pentru teste in valoare de $40$ de puncte, se garanteaza ca $1 ≤ N, K ≤ 500$.
* Pentru alte teste in valoare de $40$ de puncte, se garanteaza ca $1 ≤ N, K ≤ 5000$.

40p O(NK^2)
80p O(NK)