훈련

당신은 지역 학교의 축구 코치로서 학교를 대표할 정확히 P명의 학생으로 이루어진 팀을 선발하는 임무를 맡았다. 선발할 수 있는 학생은 N명이다. i번째 학생의 실력 점수는 $S_{i}$이며, 이는 해당 학생이 얼마나 능숙한지를 나타내는 양의 정수이다.

정확히 P명의 학생으로 이루어져 있고 모든 학생의 실력 점수가 같을 때 팀이 공정하다고 정했다. 그러면 모두가 한 팀으로 경기하게 된다. 처음에는 공정한 팀을 선발하는 것이 불가능할 수도 있으므로, 일부 학생에게 일대일 지도를 제공할 것이다. 어떤 학생이든 실력 점수를 1만큼 높이는 데 한 시간의 지도가 필요하다.

대회 시즌이 곧 시작되므로(사실 첫 경기는 이미 시작했다!), 공정한 팀을 선발할 수 있게 되기 전까지 제공해야 하는 최소 지도 시간을 구하고자 한다.

제한

시간 제한: 테스트 세트당 15초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i에 대해, 1 ≤ $S_{i}$ ≤ 10000. 2 ≤ P ≤ N.

테스트 세트 1 (공개)

2 ≤ N ≤ 1000.

테스트 세트 2 (비공개)

2 ≤ N ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 학생 수와 선발해야 하는 학생 수를 각각 나타내는 두 정수 N과 P가 포함된 줄로 시작한다. 그다음 줄에는 N개의 정수 $S_{i}$가 주어지며, 이 중 i번째 값은 i번째 학생의 실력이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 P명의 학생으로 이루어진 공정한 팀을 선발할 수 있게 되기 전까지 필요한 최소 지도 시간이다.

예제 케이스 #1에서는 첫 번째 학생을 훈련하는 데 총 6시간, 두 번째 학생을 훈련하는 데 8시간을 사용할 수 있다. 그러면 첫 번째, 두 번째, 세 번째 학생의 실력 수준이 9이 된다. 이는 사용할 수 있는 최소 시간이므로 정답은 14이다.

예제 케이스 #2에서는 아무런 지도 없이도 이미 공정한 팀(첫 번째 학생과 두 번째 학생)을 선발할 수 있으므로 정답은 0이다.

예제 케이스 #3에서는 P = N이므로 모든 학생이 팀에 속하게 된다. 세 번째 학생의 실력이 다른 모든 학생과 마찬가지로 7이 되도록 해당 학생을 6시간 동안 훈련해야 한다. 이는 사용할 수 있는 최소 시간이므로 정답은 6이다.