Fişierul intrare/ieşire:	blindpunch.in, blindpunch.out	Sursă	IIOT 2019-20 Runda 1
Autor	Alexandru Petrescu	Adăugată de	Comisia IIOT 2019-20 •unibucPoli2019
Timp execuţie pe test	1.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Blind Punch

În mijlocul nopţii ai fost atacat de gândaci. Gândacii, foarte ordonaţi formează un şir în faţa ta.
Pentru a te apăra, ai K papuci pe care îi poţi arunca pe câte un gândac (eventual poţi arunca mai mulţi papuci pe acelaşi gândac). Gândacii, foarte creativi, se prefac toţi că sunt morţi pentru a te induce în eroare (fiind întuneric poţi să vezi gândacii dar nu poţi să distingi dacă sunt striviţi sau nu).
Din fericire, ştii pentru fiecare gândac i care este probabilitatea P_i ca acesta să fie strivit printr-o aruncare de papuc (şi în cazul în care nu este strivit are tot probabilitatea P_i să fie strivit din următoarea aruncare).

Cum eşti foarte obosit şi urăşti mai mult decât orice altceva să se plimbe gândaci în jurul tău în timpul nopţii, vrei din cele K lovituri să omori cât mai mulţi gândaci.

Dându-se T astfel de scenarii, şi pentru fiecare scenariu numărul N de gândaci, numărul K de papuci, şi şirul P, unde al i-lea element al şirului reprezintă probabilitatea de a strivi al i-lea gândac dintr-o lovitură, calculează valoarea aşteptată ( expected value ) de câţi gândaci poţi strivi dacă arunci în mod optim papucii.

Cum esti foarte obosit si urasti mai mult decat orice altcv sa se plimbe gandaci in jurul tau in timpul noptii, vrei din cele K lovituri sa omori cat mai multi gandaci.

Date de intrare

Din blindpunch.in se va citi pe prima linie numărul T, reprezentând numarul de teste.
Prima linie a fiecărui test conţine numerele N şi K, reprezentând numărul de gândaci, respectiv numărul de papuci pe care îi ai la dispoziţie.
Urmatoarea linie conţine şirul P de lungime N.

Date de ieşire

În blindpunch.out se vor afişa T linii, pe linia i fiind valoarea aşteptată a numarului total de gândaci striviţi dacă arunci în mod optim papucii în al i-lea scenariu.
Numerele trebuie afişate cu EXACT 6 zecimale, rotunjite în jos.
Se garantează că a 7-a zecimală a raspunsului este în intervalul [2, 7].

Restricţii

$1 \leq N, T \leq 2 \cdot 10^5$
$1 \leq K \leq 10^6$
$\displaystyle{\sum_{i=0}^{T}N_i} \leq 2\cdot 10^5, \displaystyle{\sum_{i=0}^{T}K_i} \leq 10^6$
$0 \leq P_i \leq 1$
Pentru teste in valoare de 40 de puncte, $\displaystyle{\sum_{i=0}^{T}N_i},\ \displaystyle{\sum_{i=0}^{T}K_i},\ T \leq 500$
Pentru alte teste in valoare de 40 de puncte, $\displaystyle{\sum_{i=0}^{T}N_i}, \ \displaystyle{\sum_{i=0}^{T}K_i},\ T \leq 5000$$
Datele din input sunt date cu cel mult 9 decimale.
ATENŢIE la afişarea numerelor reale! Atunci când veţi afişa un număr asiguraţi-vă că îl afişaţi cu EXACT 6 zecimale.
Va recomandam sa faceti toate calculele folosind long double