Jonghyun, a student in KSA, made a game called Search Game to encourage the use of virtual currency of the fall school festival.

In Search Game, you must find a pre-determined integer $X (1 \le X\le N)$ through some guesses.

You input at most $K$ distinct positive integers less than or equal to $N$ in each guess.

• If the input contains $X$, the game ends.
• Otherwise, you get the number of integers less than $X$ among the current input integers.

You continue guessing until the game ends. If you made $n$ guesses in total, your final score is $(K+1)^{n-1}$.

You are a hacker trying to earn virtual currency to make Jonghyun sad and buy all the snacks and souvenirs. Find the optimal strategy minimizing your score to find the expected score.

Note that $X$ is determined before user input and the probability of $X$ being $i$ is $\frac{P_i}{P_1 + \cdots + P_N}$.

Input

The first line contains two space-separated integers $N$ and $K$.

The second line contains $N$ space-separated integers $P_1, P_2, \cdots, P_N$.

Output

Print the expected value multiplied by $(P_1 + P_2 + \cdots + P_N)$ when you use the strategy minimizing the expected value.

Constraints

• $1 \le N \le 1500$
• $1 \le K \le 5$
• $1 \le P_i \le 1000$

Scoring

Examples

Input 1

5 1
1 1 1 1 1

Output 1

13

Input 2

5 2
1 1 1 1 1

Output 2

11

Input 3

4 1
4 3 2 10

Output 3

39

Input 4

4 1
4 3 2 12

Output 4

42