급식실의 작은 시식 접시

문제

한 학교 급식실에서는 새 반찬을 정식으로 내놓기 전에 작은 시식 접시를 준비한다. 오늘 준비한 접시는 모두 N개이며, 각 접시에는 같은 반찬이 서로 다른 양으로 담겨 있다. 급식 담당자는 이 중 정확히 K개의 접시를 시식대에 올리려고 한다. 시식대에 올릴 접시를 고를 때에는 반찬의 전체 양을 가능한 한 적게 해야 한다. 시식이 끝난 뒤 남은 반찬을 처리하는 부담을 줄이기 위해서다. 접시 하나에 담긴 반찬의 양은 양의 정수로 기록되어 있으며, 선택한 접시들의 양을 모두 더한 값이 시식대에 올리는 반찬의 전체 양이다. 접시를 고르는 동안 반찬을 다른 접시로 옮기거나 덜어 내는 작업은 하지 않는다. 접시를 선택하면 그 접시에 담긴 반찬을 전부 시식대에 올려야 한다. 하나의 접시를 여러 번 선택할 수도 없다. 반찬의 양이 같은 접시가 여러 개라면 각각을 별개의 접시로 취급하므로, 그중 여러 개를 함께 골라도 된다. 접시가 입력에 나타난 순서는 선택에 영향을 주지 않는다. 앞에 적힌 접시를 먼저 골라야 한다는 규칙도 없고, 이웃한 접시끼리 골라야 한다는 규칙도 없다. 담당자는 오직 선택한 접시의 개수가 정확히 K개인지와 반찬의 전체 양이 최소인지에만 관심이 있다. 최소가 되는 선택이 여러 가지라면 접시의 번호나 선택 순서는 구분하지 않는다. 모든 입력에서는 K가 1 이상 N 이하이므로 필요한 개수의 접시를 항상 고를 수 있다. 접시별 반찬의 양이 주어졌을 때, 시식대에 올릴 수 있는 반찬의 전체 양의 최솟값을 구한다. 어떤 접시를 골랐는지는 출력하지 않고, 그 최솟값만 출력한다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ K ≤ N ≤ 1,000이다.
둘째 줄에 접시별 반찬의 양을 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 양은 1 이상 1,000 이하이다.

출력

정확히 K개의 접시를 골랐을 때 반찬의 전체 양의 최솟값을 정수 하나로 출력한다.

6 3
9 4 7 4 12 6

14

4 4
3 8 3 5

19

1 1
1

1

출처: Devin.KR 자체 제작