행운의 다시 뽑기

당신은 훌륭하고 놀라운 상품이 아주 많은(그다지 좋지 않은 상품도 일부 있는) Grand Kickstart Lucky Dip에 참가하고 있다!

이 Lucky Dip에는 N개의 물건이 든 가방이 있다. 가방 속 i번째 물건의 가치는 $V_{i}$이다. 가방에 손을 넣어 물건 하나를 무작위로 뽑으며, 가방 속 모든 물건이 선택될 확률은 같다. 주최 측은 참가자들이 어느 정도 선택권이 있다고 느끼기를 바라므로, 물건을 뽑은 뒤 그것을 가지거나 가방에 돌려놓고 다시 뽑는 "redip"을 할 수 있다. (돌려놓은 물건은 이제 가방 속 다른 어떤 물건과도 선택될 확률이 같다는 점에 유의하라.) 다시 뽑기는 최대 K번만 할 수 있다. K번의 다시 뽑기를 모두 사용했다면 (K + 1)번째로 뽑은 물건을 반드시 가져야 한다.

게임이 끝날 때 갖게 될 물건의 가치를 최대화하도록 최적으로 플레이한다면, 그 물건 가치의 기댓값은 얼마인가?

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $V_{i}$ ≤ $10^{9}$. 1 ≤ N ≤ 2 * $10^{4}$.

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 20초. 0 ≤ K ≤ 1.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 60초. 0 ≤ K ≤ 5 * $10^{4}$.

입력은 테스트 케이스의 수를 나타내는 정수 T 하나가 포함된 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄은 가방 속 물건의 수와 다시 뽑을 수 있는 최대 횟수를 나타내는 두 정수 N과 K로 이루어진다. 두 번째 줄은 N개의 정수 $V_{i}$로 이루어지며, 각각 i번째 물건의 가치를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 위에서 설명한 기댓값이다. 답이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참조하라.

예제 케이스 #1에서는 다시 뽑을 수 없으므로, 기댓값은 가방 속 물건 가치의 평균인 (1 + 2 + 3 + 4) / 4 = 2.5이다.

예제 케이스 #2에서 최선의 전략은 가치가 10인 물건을 뽑으면 그것을 가지고, 그렇지 않으면 다시 뽑는 것이다. 그 물건을 첫 번째 또는 두 번째 뽑기에서 얻을 확률은 1 - (2/3)^{2} = 5/9이므로, 기댓값은 (5/9 * 10) + (4/9 * 1) = 6이다.

예제 케이스 #3에서는 모든 물건의 가치가 같으므로 몇 번 다시 뽑는지는 중요하지 않으며, 따라서 기댓값은 80000이다.

케이스 #3과 #5은 소규모 데이터 세트에 등장하지 않는다는 점에 유의하라.