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

Poveste şi cerinţă...

In mijlocul noptii ai fost atacat de gandaci. Gandacii, foarte ordonati formeaza un sir in fata ta.
Pentru a te apara, ai $K$ papuci pe care ii poti arunca pe cate un gandac (eventual mai multi papuci pe acelasi gandac). Gandacii, foarte creativi, se prefac toti ca sunt morti pentru a te induce in eroare (fiind intuneric poti sa vezi gandacii dar nu poti sa distingi daca sunt striviti sau nu).
Din fericire, stii pentru fiecare gandac $i$ care este probabilitatea $P_i_$ ca acesta sa fie strivit printr-o aruncare de papuc (si in caz ca nu este strivit are tot probabilitatea $P_i_$ sa fie strivit din a doua aruncare etc).
 
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.
 
h2. Cerinta
 
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

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

Datele de intrare se citesc din fisierul $blindpunch.in$.
 
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$.

h2. Date de ieşire

În fişierul de ieşire $blindpunch.out$ ...

Datele de iesire se afiseaza in fisierul $blindpunch.out$.
 
Afisati expectedul numarului total de gandaci striviti daca aruncati in mod optim papucii.

h2. Restricţii

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

* $1 ≤ N, K ≤ 10^6^$
* $0 ≤ P_i_ ≤ 1$
* 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)
100p O((N+K)logN)
 
 

h2. Exemplu