럭키 딥

여러분은 굉장하고 멋진 상품들(그리고 그다지 좋지 않은 상품들도 몇 개)이 걸린 Grand Kickstart 럭키 딥에 참가하고 있다!

이 럭키 딥에는 N개의 물건이 들어 있는 주머니가 있다. 주머니에 있는 i번째 물건의 가치는 Vi이다. 주머니에 손을 넣어 물건 하나를 무작위로 뽑는다. 주머니 안의 모든 물건은 뽑힐 확률이 같다. 주최 측은 참가자들이 선택의 여지가 있다고 느끼기를 바라므로, 물건을 뽑은 뒤에 그것을 그대로 가질 수도 있고, 주머니에 되돌려 놓고 다시 뽑는 "리딥"을 할 수도 있다. (되돌려 놓은 물건은 이제 주머니 안의 다른 물건들과 똑같은 확률로 뽑힌다.) 리딥은 최대 K번까지 할 수 있다. 리딥을 K번 모두 사용했다면, (K + 1)번째로 뽑은 물건을 반드시 가져야 한다.

게임을 끝낼 때 가지게 되는 물건의 가치를 최대로 만들도록 최적으로 플레이한다면, 그 물건 가치의 기댓값은 얼마인가?

첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 주머니 안 물건의 수 N과 리딥할 수 있는 최대 횟수 K가 주어진다. 둘째 줄에는 N개의 정수 Vi가 주어지며, 각각 i번째 물건의 가치를 나타낸다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 기댓값이다. 정답과의 절대 오차 또는 상대 오차가 10-6 이내이면 정답으로 인정된다.

• 1 ≤ T ≤ 100.
• 1 ≤ Vi ≤ 109.
• 1 ≤ N ≤ 2 * 104.

예제 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는 Small 데이터셋에는 나오지 않는다.