지원 도구 버전 맞추기

문제

한 회사의 IT 지원팀은 직원용 컴퓨터에 설치된 사내 지원 도구를 관리한다. 지원 도구의 버전은 0부터 999까지의 정수로 표시한다. 서로 다른 버전이 설치된 컴퓨터로도 평소 업무는 가능하지만, 이번 점검에서는 선택한 컴퓨터들이 모두 같은 버전을 사용해야 한다. 지원팀은 전체 N대 중 정확히 K대를 골라 점검할 예정이다. 점검 대상으로 고른 컴퓨터는 모두 하나의 공통 목표 버전 T로 맞춘다. T 역시 0부터 999까지의 정수여야 한다. 버전을 낮추는 작업은 허용하지 않으므로, 선택한 컴퓨터의 현재 버전이 하나라도 T보다 크면 그 선택과 목표 버전의 조합은 사용할 수 없다. 현재 버전이 T와 같은 컴퓨터는 별도 작업 없이 점검에 참여한다. 현재 버전이 V인 컴퓨터를 T로 올릴 때 필요한 작업량은 T−V이다. 여러 단계를 한꺼번에 올리더라도 작업량은 같은 차이로 계산한다. 선택한 K대의 작업량을 모두 더한 값을 총 작업량이라고 한다. 선택하지 않은 컴퓨터에는 아무 작업도 하지 않으며, 그 컴퓨터의 버전은 총 작업량에 영향을 주지 않는다. 컴퓨터들이 입력에 놓인 순서는 선택 가능 여부와 관계가 없다. 지원팀은 가능한 모든 컴퓨터 선택과 목표 버전 중에서 총 작업량이 가장 작은 방법을 사용한다. 최소 총 작업량을 얻는 목표 버전이 여러 개라면, 그중 가장 작은 목표 버전을 택한다. 같은 총 작업량과 같은 목표 버전을 만드는 컴퓨터 선택이 여러 개라면 어느 선택을 사용해도 되며, 선택한 컴퓨터의 번호는 출력하지 않는다. 현재 버전이 같은 컴퓨터도 각각 별개의 컴퓨터로 센다. 예를 들어 같은 버전의 컴퓨터가 충분히 많다면 작업량이 0인 점검을 할 수 있다. K가 1이면 컴퓨터 한 대만 선택한다. K가 N이면 모든 컴퓨터를 선택한다. 모든 입력에서는 조건을 만족하는 점검 방법이 존재한다. 최소 총 작업량과 동점 규칙에 따라 정한 목표 버전을 구한다.

입력

첫째 줄에 컴퓨터 수 N과 선택할 컴퓨터 수 K가 주어진다. 1≤K≤N≤100,000이다.
둘째 줄에 각 컴퓨터의 현재 버전 V₁, V₂, …, Vₙ이 공백으로 구분되어 주어진다. 0≤Vᵢ≤999이다. 모든 입력값은 정수이다.

출력

최소 총 작업량과 선택한 목표 버전을 이 순서대로 한 줄에 공백으로 구분하여 출력한다.

6 3
9 2 8 3 7 3

1 3

4 2
8 4 8 4

0 4

3 3
0 5 2

8 5

출처: Devin.KR 자체 제작