CF2181J 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 \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.

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