P14791 [NERC 2025] Jinx or Jackpot

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