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 integer choices each from 0 to 100. He picked an index () 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 . And he created it.
Jack knows the array of choices that suddenly appeared to the owner during the walk, but he does not know which the owner picked. However, the chosen index is fixed forever; the slot machine always uses the same as explained below.
On the slot machine, Jack can bet dollars, where is a non-negative integer, and pull the lever. Then:
With probability it will be a jackpot, and the slot machine returns dollars to him, so he gains dollars.
With probability it will be a jinx, and the slot machine returns nothing to him, so he loses 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 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 and () — the number of choices and the limit on the number of rounds. The second line contains integers () — 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 .
