묶음별 높이 차이

문제

물류 창고에서는 출고할 상자들을 여러 검사 묶음으로 나누어 높이를 확인한다. 검사대의 안내판에는 각 묶음에서 가장 높은 상자와 가장 낮은 상자의 높이 차이가 표시된다. 창고 관리자는 모든 검사 묶음에 표시되는 높이 차이를 더하여 오늘의 검사 기록으로 남기려 한다. 상자의 높이와 묶음의 기준 크기가 주어졌을 때 이 합을 구하는 프로그램을 작성한다. 검사 묶음은 정해진 절차로 만든다. 먼저 모든 상자를 높이가 작은 것부터 큰 것 순서로 정렬한다. 그다음 정렬된 순서의 맨 앞에서부터 K개씩 잘라 하나의 묶음으로 만든다. 마지막에 남은 상자가 K개보다 적으면 남은 상자만으로 마지막 묶음을 만든다. 남은 상자가 없으면 빈 묶음을 추가하지 않는다. 각 상자는 정확히 하나의 묶음에 들어간다. 각 묶음의 높이 차이는 그 묶음에 들어 있는 상자의 최대 높이에서 최소 높이를 뺀 값이다. 상자가 하나뿐인 묶음의 높이 차이는 0이다. 같은 높이의 상자가 여러 개 있어도 각각 별개의 상자로 센다. 높이가 같은 상자 사이의 순서는 자유롭게 정할 수 있으며, 그 순서에 따라 구하려는 합이 달라지지는 않는다. 입력에 적힌 상자의 순서는 정렬하기 전의 순서다. 묶음을 만들 때에는 반드시 전체 상자를 먼저 정렬한 결과를 사용한다. 높이 차이의 합을 줄이기 위해 묶음의 크기나 경계를 임의로 바꾸지 않는다. 모든 높이는 같은 단위로 측정한 양의 정수이며, 출력할 때에는 단위를 붙이지 않는다. 묶음이 하나만 만들어지는 경우에도 같은 계산 규칙을 적용한다.

입력

첫째 줄에 상자 수 N과 묶음의 기준 크기 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ K ≤ N ≤ 50,000이다.
둘째 줄에 N개 상자의 높이가 공백으로 구분되어 주어진다. 각 높이는 1 이상 999 이하의 정수다.

출력

정해진 절차로 만든 모든 묶음의 높이 차이를 더한 값을 정수 하나로 출력한다.

7 3
8 2 9 2 5 7 1

4

4 1
6 2 6 9

0

5 5
12 12 12 12 12

0

출처: Devin.KR 자체 제작