Problem 1614: Blind Punch

In the middle of the night you have been attacked by bugs. The bugs are very well organised and form a line in front of you.

In order to protect yourself you have $K$ slippers that you will throw at the bugs one at a time (eventually you can throw multiple slippers at the same bug). The bugs, being very creative, are playing dead in order to fool you (the room is poorly illuminated and you can see the bugs, but you cannot tell which ones are squashed and which are alive).

Fortunately, you know for the $i^{th}$ bug what is the probability $P_i$ that it will be squashed by a single slipper (in the case in which the bug is not squashed, the next time you throw a slipper at it, the probability $P_i$ will stay the same).

As you are very tired and hate bugs crawling around in your room in the middle of the night you want to use the $K$ slippers you have at your disposal to squash as many bugs as possible.

Given $T$ such scenarios and for each scenario the number of bugs $N$ , the number of slippers $K$ and the array $P$ , calculate the expected value of the total number of squashed bugs if you throw the slippers optimally.

Input data

The first line will contain the number $T$ , representing the number of scenarios.

Every first line of each such scenario contains the numbers $N$ and $K$ , the number of bugs and the number of slippers you have. The next line of each test contains the array $P$ of length $N$ .

Output data

You will print $T$ lines, on the $i^{th}$ line being the expected value of the total number of squashed bugs if you optimally throw the slippers in the $i^{th}$ scenario.

The printed numbers have to have EXACTLY $6$ decimals, rounded down. It is guaranteed that the $7^{th}$ decimal of the answer is inside the interval $[2, 7]$ .

Constraints and clarifications

$1 \leq N, T \leq 2 \cdot 10^5$
$1 \leq K \leq 10^6$
$\sum_{i=0}^{T}N_i \leq 2\cdot 10^5$ , $\sum_{i=0}^{T}K_i \leq 10^6$
$0 \leq P_i \leq 1$
For tests worth $40$ points: $\sum_{i=0}^{T}N_i$ , $\sum_{i=0}^{T}K_i,\ T \leq 500$
For other tests worth $40$ points: $\sum_{i=0}^{T}N_i$ , $\sum_{i=0}^{T}K_i,\ T \leq 5000$
The real numbers from the input have at most $9$ decimals.
PAY ATTENTION to printing real numbers! When you will print a number, make sure that you print EXACTLY $6$ decimals.
We recommand that you do all calculations using long double.

Example 1

stdin

2
5 5 
0.9 0.7 0.5 0.3 0.1
4 2
0.1 0.1 0.5 0.5

stdout

2.650000
1.00000

Explanation

THIS EXAMPLE DOES NOT MEET THE CRITERION INVOLVING THE LAST DECIMAL DIGIT

Example 2