함께 출차할 차량 묶음

문제

한 주차장은 같은 시각에 입차한 차량들을 대상으로 묶음 출차 서비스를 시험한다. 각 차량의 운전자는 입차할 때 희망 주차 시간을 분 단위의 정수로 제출한다. 주차장 관리자는 신청한 N대 가운데 정확히 K대를 골라 하나의 서비스 묶음으로 정하려 한다. 차량이 입력된 순서는 접수 순서일 뿐이며, 선택할 차량들이 접수 순서에서 이웃할 필요는 없다. 하나의 묶음에 속한 차량들은 비슷한 시각에 출차하는 편이 운영하기 좋다. 관리자는 선택한 차량들의 희망 주차 시간 중 가장 큰 값에서 가장 작은 값을 뺀 값을 시간 차이라고 정의한다. 첫 번째 목표는 이 시간 차이가 가능한 한 작은 묶음을 고르는 것이다. K가 1이면 가장 큰 값과 가장 작은 값이 같으므로 시간 차이는 0이다. 시간 차이가 가장 작은 묶음이 여러 개라면, 선택한 차량들의 희망 주차 시간을 모두 더한 값이 가장 작은 묶음을 고른다. 이는 다른 조건이 같을 때 더 이른 출차를 원하는 차량들을 우선하기 위한 규칙이다. 두 기준의 우선순서는 바뀌지 않는다. 주차 시간 합계가 더 작더라도 시간 차이가 더 크면 선택하지 않는다. 희망 주차 시간이 같은 차량도 각각 별개의 차량이다. 예를 들어 같은 값을 제출한 차량이 세 대 있으면 그중 두 대를 선택할 수 있으며, 이때 합계에는 해당 값을 두 번 더한다. 두 기준을 모두 적용한 뒤에도 여러 묶음이 남을 수 있지만, 이 문제에서는 차량 번호를 출력하지 않으므로 추가 선택 규칙은 필요하지 않다. 최소 시간 차이와 그 시간 차이를 달성하는 묶음 중 최소 주차 시간 합계를 구한다. 항상 1 ≤ K ≤ N이므로 선택할 수 있는 묶음은 적어도 하나 존재한다.

입력

첫째 줄에 차량 수 N과 선택할 차량 수 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 각 차량의 희망 주차 시간 T_1, T_2, …, T_N이 공백으로 구분되어 주어진다. 1 ≤ T_i ≤ 99이며 단위는 분이다. 모든 수는 정수이다.

출력

가능한 최소 시간 차이와, 그 시간 차이를 달성하는 묶음 중 최소 주차 시간 합계를 공백으로 구분하여 한 줄에 출력한다.

6 3
12 4 8 5 11 6

2 15

5 2
9 7 3 1 5

2 4

4 3
8 8 8 8

0 24

출처: Devin.KR 자체 제작