이미지 레이블러

Crowdsource는 $\mathbf{N}$개 지역의 참가자를 대상으로 Image Labeler 과제 캠페인을 진행한다. 지역 $i$의 참가자 수는 $\mathbf{A\_i}$명이다. 과제에는 $\mathbf{M}$개의 범주가 있다. Crowdsource는 한 지역의 참가자를 모두 같은 범주에 배정하며, 모든 범주에는 최소 한 개의 지역이 배정되어야 한다.

성과 지표는 각 범주에 속한 참가자 수 중앙값의 총합이다. 정수 목록의 중앙값은 오름차순으로 정렬했을 때 가운데에 놓인 값이다. 원소 개수가 짝수이면 가운데 두 값의 평균이 중앙값이다.

예를 들어 $\mathbf{N}=3$, $A\_1=5$, $A\_2=8$, $A\_3=9$, $\mathbf{M}=2$인 경우를 보자. 지역 2와 3을 범주 1에, 지역 1을 범주 2에 배정하면 $\{8, 9\}$의 중앙값과 $\{5\}$의 중앙값을 더해 $\frac{8+9}{2} + 5 = 13.5$가 된다. 지역 1과 2를 범주 1에, 지역 3을 범주 2에 배정하면 $\frac{5+8}{2} + 9 = 15.5$가 된다.

성과 지표의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 각 테스트 케이스의 첫 줄에는 지역의 수 $\mathbf{N}$과 범주의 수 $\mathbf{M}$이 주어진다. 다음 줄에는 $\mathbf{A\_1}, \mathbf{A\_2}, \dots, \mathbf{A\_N}$이 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 성과 지표의 최댓값이다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.

• $1 \le \mathbf{T} \le 100$.
• $1 \le \mathbf{N} \le 10^4$.
• $1 \le \mathbf{M} \le 10^4$.
• $1 \le \mathbf{M} \le \mathbf{N}$.
• 모든 $i$에 대해 $1 \le \mathbf{A\_i} \le 10^5$.