Search Game

Jonghyeon, a student at KSA, made a search game to boost virtual currency trading at the autumn school festival. In the search game, an integer $X$ ($1 \le X \le N$) is fixed before the game starts, and you find its value by asking the right questions. In each question, the player enters at most $K$ distinct positive integers not greater than $N$. If $X$ is among the entered values, the game ends. Otherwise, the player receives the number of entered integers that are less than $X$. This process repeats until the game ends. If the game takes $n$ questions, the final score is $(K+1)^{n-1}$ points. You are a hacker who wants to earn virtual currency and take all the snacks and souvenirs from Jonghyeon. Find the strategy that minimizes the expected score of the search game, and print that expected value. The value $X$ is fixed before the player enters anything, and the probability that $X$ is $i$ is $\frac{P_i}{P_1 + \cdots + P_N}$.

The first line contains two integers $N$ and $K$, separated by a space. The second line contains $N$ integers $P_1, P_2, \cdots, P_N$, separated by spaces.

Print the expected score under the optimal strategy, multiplied by $(P_1 + P_2 + \cdots + P_N)$.

$1\leq N\leq 1500$, $1\leq K \leq 5$, $1\leq P_i\leq 1000$.