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

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. Restricţii
* $1 ≤ N, K ≤ 10^6^$

* $0 ≤ P_i_ ≤ 1$

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