Training
면접 대비시간 제한15초메모리 제한1024 MB
정확히 P명의 학생을 골라 모두 같은 스킬 값이 되도록 1시간에 1씩 올릴 때 필요한 최소 총 시간을 구한다.
문제
지역 학교의 축구 코치인 당신은 학교를 대표할 정확히 P명의 학생으로 이루어진 팀을 뽑아야 한다. 선택할 수 있는 학생은 N명이다. i번째 학생의 실력 등급은 Si이며, 이는 실력이 얼마나 뛰어난지를 나타내는 양의 정수이다.
팀이 공정하다는 것은 정확히 P명의 학생으로 구성되고 그들 모두의 실력 등급이 같다는 뜻이다. 그래야 모두가 하나의 팀으로 뛸 수 있다. 처음에는 공정한 팀을 뽑지 못할 수도 있으므로, 일부 학생에게 일대일 코칭을 해 줄 것이다. 어떤 학생의 실력 등급을 1 올리는 데는 1시간의 코칭이 걸린다.
대회 시즌이 곧 시작된다(사실 첫 경기는 이미 시작했다!). 공정한 팀을 뽑을 수 있게 되기 전까지 해 줘야 하는 코칭 시간의 최솟값을 구하라.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N과 P가 주어지며, 이는 각각 학생의 수와 뽑아야 하는 학생의 수이다. 그다음 줄에는 N개의 정수 Si가 주어진다. 이 중 i번째 값은 i번째 학생의 실력이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 P명의 학생으로 이루어진 공정한 팀을 뽑을 수 있게 되기 전까지 필요한 코칭 시간의 최솟값이다.
제한
- 1 ≤ T ≤ 100.
- 모든 i에 대해 1 ≤ Si ≤ 10000.
- 2 ≤ P ≤ N.
힌트
예제 1에서는 첫 번째 학생을 6시간, 두 번째 학생을 8시간 훈련하면 총 14시간이 걸린다. 그러면 첫 번째, 두 번째, 세 번째 학생의 실력이 9가 된다. 이보다 적은 시간을 쓸 수 없으므로 답은 14이다.
예제 2에서는 코칭 없이 이미 공정한 팀(첫 번째와 두 번째 학생)을 뽑을 수 있으므로 답은 0이다.
예제 3에서는 P = N이므로 모든 학생이 팀에 들어간다. 세 번째 학생이 다른 학생들처럼 실력 7이 되도록 6시간을 훈련해야 한다. 이보다 적은 시간을 쓸 수 없으므로 답은 6이다.