점검 묶음의 예상 시간

문제

한 회사의 사내 IT 지원팀은 업무용 장비의 정기 점검을 준비하고 있다. 이번 점검 대상 장비는 N대이며, 각 장비를 점검하는 데 걸리는 예상 시간이 분 단위의 양의 정수로 정리되어 있다. 지원팀은 첫 번째 작업 묶음에 정확히 K대의 장비를 넣으려고 한다. 첫 번째 묶음을 빨리 끝내기 위해 예상 시간이 짧은 장비부터 K대를 고르는 규칙을 정했다. 장비의 예상 시간은 담당자가 조사한 순서대로 입력된다. 입력 순서는 예상 시간의 크기와 관계가 없으므로, 앞에서부터 K대를 고르는 것은 팀의 규칙과 다를 수 있다. 모든 장비의 예상 시간을 짧은 순서로 정렬한 뒤, 그중 앞의 K개를 선택해야 한다. 같은 예상 시간을 가진 장비가 여러 대라면 어느 장비를 먼저 선택해도 된다. 이 문제에서는 선택한 장비의 번호를 출력하지 않으므로 같은 시간 사이의 순서는 결과에 영향을 주지 않는다. 점검은 한 명의 담당자가 장비를 한 대씩 차례로 처리하는 방식으로 진행한다. 여러 장비를 동시에 점검할 수 없으며, 장비 사이를 이동하거나 다음 장비를 준비하는 데 드는 시간은 없다고 본다. 따라서 선택한 K대의 점검을 모두 끝내는 데 필요한 예상 시간은 선택한 장비들의 예상 시간을 더한 값이다. 아직 선택하지 않은 나머지 장비의 점검 시간은 첫 번째 묶음의 예상 시간에 포함하지 않는다. 지원팀이 정한 규칙에 따라 첫 번째 작업 묶음을 구성했을 때, 그 묶음의 전체 예상 시간을 구하는 프로그램을 작성한다. 장비는 반드시 K대를 골라야 하며, K가 N과 같다면 모든 장비를 첫 번째 묶음에 넣는다. 예상 시간이 같은 장비도 각각 별도의 장비이므로, 같은 값이 여러 번 나타나면 나타난 횟수만큼 선택할 수 있다.

입력

첫째 줄에 장비 수 N과 첫 번째 작업 묶음에 넣을 장비 수 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ K ≤ N ≤ 1,000이다.
둘째 줄에 각 장비의 예상 점검 시간 T₁, T₂, …, Tₙ이 공백으로 구분되어 주어진다. 각 Tᵢ는 1 이상 10,000 이하인 정수이며 단위는 분이다.

출력

예상 점검 시간이 짧은 장비부터 정확히 K대를 선택했을 때, 선택한 장비들의 예상 점검 시간 합을 정수로 출력한다. 같은 예상 시간 사이의 선택 순서는 자유이며, 선택한 장비의 번호는 출력하지 않는다.

6 3
18 7 12 7 25 4

18

4 4
9 2 9 5

25

5 2
8 8 8 8 8

16

출처: Devin.KR 자체 제작