IT 지원팀의 용량 구간

문제

사내 IT 지원팀이 직원들의 업무용 노트북을 새 저장 장치로 옮기려 한다. 각 노트북에서 옮길 데이터의 용량은 미리 측정되어 있다. 지원팀은 작업을 정확히 K개의 묶음으로 나누고, 각 묶음에 맞는 전송 설정을 하나씩 준비한다. 작업 순서와 담당 직원은 이미 확보되어 있으므로 이 문제에서는 묶음을 정하는 데 드는 준비 비용만 고려한다. 하나의 묶음에는 노트북이 적어도 한 대 있어야 한다. 모든 노트북은 정확히 하나의 묶음에 속해야 하며, 한 묶음에 넣을 수 있는 노트북 수에는 제한이 없다. 입력에서 서로 떨어져 있는 노트북도 같은 묶음에 넣을 수 있다. 노트북의 입력 순서나 직원의 소속은 묶음을 정할 때 아무런 제약을 만들지 않는다. 한 묶음의 전송 설정은 그 묶음에서 가장 작은 데이터 용량부터 가장 큰 데이터 용량까지를 처리하도록 준비한다. 지원팀은 이 범위의 폭을 준비 비용으로 사용한다. 따라서 한 묶음의 비용은 그 묶음에 속한 노트북의 최대 용량에서 최소 용량을 뺀 값이다. 노트북이 한 대뿐인 묶음의 비용은 0이다. 같은 용량의 노트북만 여러 대 들어 있는 묶음의 비용도 0이다. 전체 준비 비용은 K개 묶음의 비용을 모두 더한 값이다. 지원팀은 전체 준비 비용이 가장 작아지도록 묶음을 정하려 한다. 같은 용량의 노트북들이 서로 다른 묶음에 들어가도 된다. 비용이 같은 묶음 구성이 여러 개라면 어느 구성을 선택해도 되며, 구성 자체를 출력할 필요는 없다. K가 노트북 수와 같으면 각각을 한 묶음으로 만들 수 있다. 모든 노트북을 빠짐없이 정확히 K개의 비어 있지 않은 묶음으로 나눌 때 가능한 전체 준비 비용의 최솟값을 구한다.

입력

첫째 줄에 노트북 수 N과 묶음 수 K가 공백으로 주어진다.
둘째 줄에 각 노트북의 데이터 용량을 나타내는 정수 X_1, X_2, ..., X_N이 공백으로 주어진다.
1 ≤ K ≤ N ≤ 50,000이며 0 ≤ X_i ≤ 1,000,000이다. 용량의 단위는 동일하며, 같은 용량이 여러 번 주어질 수 있다.

출력

가능한 전체 준비 비용의 최솟값을 정수 하나로 출력한다. 최솟값이 0이면 0을 출력한다.

6 2
8 20 9 30 21 22

11

7 3
4 4 10 13 14 30 31

5

1 1
0

0

출처: Devin.KR 자체 제작