题目描述

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 \le i \le 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.

输入格式

The first line contains two integers $n$ and $k$ ($1 \le n \le 100\,000; 1 \le k \le 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 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}$.

2 2
70 30

160

2 30
30 70

12099716.1778528057038784

2 5
40 50

0

6 6
10 20 60 30 40 50

29.40799999999990177457221

1 5
61

1702.708163199999489734182