이미지 라벨러

Crowdsource는 $\mathbf{N}$개 지역의 참가자들과 함께 Image Labeler 작업을 위한 캠페인을 준비하고 있다. 각 지역의 참가자 수는 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}$로 나타낸다.

이미지 라벨러 작업에는 $\mathbf{M}$개의 범주가 있다. Crowdsource는 한 지역의 모든 참가자가 같은 범주에 배정되고 각 범주에 적어도 한 지역이 배정되도록 참가자들을 이 범주들에 배정한다. 캠페인의 성공 지표는 각 범주에 속한 참가자 수의 중앙값을 합한 값으로 측정한다. (정수 목록의 중앙값은 해당 정수들을 작은 것부터 큰 것까지 정렬했을 때 "middle" 수라는 점을 여기서 다시 알려 둔다. 목록에 있는 정수의 개수가 짝수이면 "middle" 수가 두 개이므로, 중앙값은 가운데 두 값의 산술 평균(평균값)으로 정의한다.)

예를 들어 참가자가 각각 $\mathbf{A_1}=5$, $\mathbf{A_2}=8$, $\mathbf{A_3}=9$명인 $\mathbf{N}=3$개 지역을 $\mathbf{M}=2$개 범주에 배정한다고 하자. 지역 $2$과 $3$를 범주 $1$에 배정하고 지역 $1$를 범주 $2$에 배정하면, 성공 지표는 $\{A_2=8, A_3=9\}\ +$의 중앙값 $\{A_1=5\} = \frac{8 + 9}{2} + 5 = 8.5 + 5 = 13.5$의 중앙값이 된다. 지역 $1$과 $2$를 범주 $1$에 배정하고 지역 $3$를 범주 $2$에 배정할 수도 있다. 그러면 성공 지표는 $\{A_1=5, A_2=8\}$의 중앙값과 $\{A_3=9\}$의 중앙값을 합한 값과 같으며, 이는 $\frac{5+8}{2} + 9 = 6.5 + 9 = 15.5$이다.

지역의 참가자들을 범주에 배정하여 얻을 수 있는 성공 지표의 가능한 최댓값을 구하라.

제한

메모리 제한: 1 GB. $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$.

테스트 세트 1

시간 제한: 20초. $0 \le \mathbf{N} - \mathbf{M} \le 1$.

테스트 세트 2

시간 제한: 40초. 추가 제약 조건은 없다.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 지역의 수와 범주의 수를 각각 나타내는 두 정수 $\mathbf{N}$과 $\mathbf{M}$가 주어진다. 다음 줄에는 $\mathbf{N}$개의 정수 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 (1부터 시작하는) 테스트 케이스 번호이고, $y$는 성공 지표의 가능한 최댓값이다.

$y$가 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 간주한다. 이것이 의미하는 바와 허용되는 실수 형식에 관한 설명은 FAQ을 참조하라.

이 테스트에서는 지역의 참가자들을 $6$가지 가능한 방법으로 범주에 배정할 수 있다:

• $\{11, 24\}$를 범주 $1$에 배정하고 $\{10\}$를 범주 $2$에 배정한다. 이 경우 성공 지표는 $\frac{11 + 24}{2} + 10 = 17.5 + 10 = 27.5$이다.

• $\{24, 10\}$를 범주 $1$에 배정하고 $\{11\}$를 범주 $2$에 배정한다. 이 경우 성공 지표는 $\frac{24 + 10}{2} + 11 = 17 + 11 = 28$이다.

• $\{11, 10\}$를 범주 $1$에 배정하고 $\{24\}$를 범주 $2$에 배정한다. 이 경우 성공 지표는 $\frac{11 + 10}{2} + 24 = 10.5 + 24 = 34.5$이다.

• 그 밖의 $3$가지 방법에서는 범주 $1$와 $2$에 대한 배정이 서로 바뀌며, 이는 성공 지표의 값을 바꾸지 않는다.

따라서 성공 지표의 가능한 최댓값은 $34.5$이다.

추가 예제 - 테스트 세트 2

이 테스트에는 범주가 하나뿐이므로 모든 지역의 참가자가 그 범주에 배정된다. 성공 지표로 가능한 유일한 값은 $\{6, 2, 5, 1, 9\}$의 중앙값인 $5$이다.