지원 시간에 맞춘 요청 묶음

문제

한 회사의 IT 지원 담당자는 점검 시간에 처리할 요청 묶음을 만들고 있다. 접수된 요청은 모두 N개이며, 각 요청을 끝내는 데 필요한 작업 시간은 미리 조사되어 있다. 요청에는 장비 연결 확인이나 계정 설정 점검처럼 서로 독립적인 작업만 들어 있다. 따라서 어떤 요청을 선택하더라도 다른 요청의 작업 시간이 바뀌거나 추가 작업이 생기지 않는다. 이번 점검 시간에는 정확히 K개의 요청을 처리하기로 했다. 담당자는 선택한 요청을 한 번에 하나씩 처리하며, 요청 사이에 이동하거나 준비하는 시간은 없다고 가정한다. 한 요청을 여러 번 선택할 수 없고, 선택한 요청은 중간에 나누지 않고 끝까지 처리해야 한다. 선택하지 않은 요청은 다음 점검 시간으로 넘기므로 이번 작업 시간에 포함하지 않는다. 담당자가 원하는 것은 정확히 K개를 처리하면서 실제 작업에 쓰는 전체 시간을 가장 짧게 만드는 것이다. 전체 작업 시간은 선택한 요청들의 작업 시간을 더한 값이다. 처리 순서는 이 합에 영향을 주지 않는다. 작업 시간이 같은 요청도 서로 다른 요청이므로 각각 하나씩 선택할 수 있다. 예를 들어 작업 시간이 4인 요청이 두 개라면 둘을 모두 선택했을 때 요청 수는 두 개이고 필요한 시간은 8이다. 최소 시간을 만드는 요청 묶음이 여러 개일 수 있다. 이 문제에서는 어느 요청을 골랐는지 출력하지 않고 최소 시간만 출력하므로, 같은 시간을 만드는 묶음 사이에 별도의 우선순위는 없다. K가 0이면 이번 점검 시간에는 아무 요청도 처리하지 않으며 전체 작업 시간은 0이다. 접수된 모든 요청의 작업 시간과 K가 주어질 때, 조건에 맞는 요청 묶음의 최소 전체 작업 시간을 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ K ≤ N이다.
둘째 줄에 각 요청의 작업 시간을 나타내는 정수 T_1, T_2, …, T_N이 주어진다. 모든 i에 대해 1 ≤ T_i ≤ 10,000이며, 시간의 단위는 분이다.

출력

정확히 K개의 요청을 선택했을 때 가능한 최소 전체 작업 시간을 정수 하나로 출력한다. K가 0이면 0을 출력한다.

6 3
9 4 7 4 12 2

10

4 0
3 8 3 5

0

3 3
6 6 1

13

출처: Devin.KR 자체 제작