J. Jinx or Jackpot
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jack is in his favourite casino and has $$$1000$$$ dollars. The casino has literally nothing but a single slot machine. Jack knows the history of this casino. Once upon a time, the future owner of the casino was walking and suddenly saw an array of $$$n$$$ integer choices $$$p_{1}, \dots, p_{n}$$$ each from $$$0$$$ to $$$100$$$. He picked an index $$$i$$$ ($$$1 \leq i \leq n$$$) uniformly at random and thought that it was a good idea to create a casino in which there is only one slot machine with jackpot probability of $$$\frac{p_i}{100}$$$. And he created it.

Jack knows the array of choices $$$p_{1}, \dots, p_{n}$$$ that suddenly appeared to the owner during the walk, but he does not know which $$$i$$$ the owner picked. However, the chosen index $$$i$$$ is fixed forever; the slot machine always uses the same $$$p_i$$$ as explained below.

On the slot machine, Jack can bet $$$x$$$ dollars, where $$$x$$$ is a non-negative integer, and pull the lever. Then:

  1. With probability $$$\frac{p_i}{100}$$$ it will be a jackpot, and the slot machine returns $$$2x$$$ dollars to him, so he gains $$$x$$$ dollars.
  2. With probability $$$1 - \frac{p_i}{100}$$$ it will be a jinx, and the slot machine returns nothing to him, so he loses $$$x$$$ dollars.

Even if Jack bets $$$0$$$ dollars, he will understand whether it was a jinx or a jackpot.

Also, the slot machine is not very durable, so Jack can play at most $$$k$$$ rounds on it.

Find the maximum expected profit Jack can achieve by an optimal strategy. Here a profit is defined as the final amount of money Jack has minus his initial $$$1000$$$ dollars.

Of course, Jack can't make a bet that is more than his current balance.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 100\,000$$$; $$$1 \leq k \leq 30$$$) — the number of choices and the limit on the number of rounds. The second line contains $$$n$$$ integers $$$p_{1}, \dots, p_{n}$$$ ($$$0 \le p_i \le 100$$$) — the choices.

Output

Output a single real number — the expected profit Jack can achieve by an optimal strategy. Your answer will be considered correct if its absolute or relative error is at most $$$10^{-4}$$$.

Examples
Input
2 2
70 30
Output
160
Input
2 30
30 70
Output
12099716.1778528057038784
Input
2 5
40 50
Output
0
Input
6 6
10 20 60 30 40 50
Output
29.40799999999990177457221
Input
1 5
61
Output
1702.708163199999489734182