탐색 게임

KSA 학생 종현이는 가을 학교 축제에서 축제용 가상화폐 거래를 활성화하려고 탐색 게임을 만들었다. 탐색 게임은 게임을 시작할 때 미리 정해진 정수 $X$ ($1 \le X \le N$)의 값을 적절한 질문으로 맞히는 게임이다. 매 질문마다 사용자는 서로 다른 $N$ 이하의 양의 정수를 $K$개 이하로 골라 입력한다. 입력한 값 중에 $X$가 있으면 게임이 종료된다. 그렇지 않으면 방금 입력한 정수 중 $X$보다 작은 정수의 개수가 사용자에게 주어진다. 게임이 종료될 때까지 이 과정이 반복된다. 게임에서 $n$번 질문했다면 최종 점수는 $(K+1)^{n-1}$점이다. 여러분은 게임에서 가상화폐를 벌어 종현이를 울리고 모든 간식과 기념품을 쓸어가려는 해커다. 탐색 게임을 수행하여 얻는 점수의 기댓값을 최소화하는 전략을 찾고, 그 기댓값을 출력하라. 단, 정답 값 $X$는 사용자가 입력하기 전에 정해지며, $X$가 $i$일 확률은 $\frac{P_i}{P_1 + \cdots + P_N}$이다.

첫 번째 줄에 두 정수 $N$, $K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $N$개의 정수 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다.

최적의 전략을 사용했을 때의 기댓값에 $(P_1 + P_2 + \cdots + P_N)$을 곱한 값을 출력한다.

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