점검할 게임 서버 고르기

문제

한 게임 서비스는 여러 대의 게임 서버를 운영한다. 운영 담당자는 정기 점검을 시작하기 전에 서버마다 현재 처리 중인 작업의 수를 조사했다. 서버를 점검 상태로 바꾸려면 그 서버에서 처리 중인 작업을 모두 다른 서버로 옮겨야 한다. 따라서 처리 중인 작업이 적은 서버를 고르면 점검 준비에 필요한 작업 이동을 줄일 수 있다. 이번 점검에서는 전체 N대 중 정확히 K대를 골라야 한다. 각 서버에서 처리 중인 작업의 수가 주어질 때, 선택한 서버들의 작업 수 합이 가능한 한 작아지도록 고른다. 이때 얻을 수 있는 작업 수 합의 최솟값을 구하는 프로그램을 작성한다. 서버 한 대는 한 번만 선택할 수 있다. 처리 중인 작업이 없는 서버도 선택할 수 있으며, 그런 서버를 선택하면 합에 0을 더한다. 선택하지 않은 서버의 작업 수는 합에 포함하지 않는다. 작업을 옮기는 과정에서 새로운 작업이 생기거나 기존 작업이 사라지는 일은 없으며, 실제로 작업을 어느 서버로 옮길지는 계산하지 않는다. 입력에 주어진 작업 수만으로 선택 비용을 계산한다. 작업 수가 같은 서버가 여러 대라면 그중 어느 서버를 선택해도 된다. 작업 수 합이 같은 선택 방법이 여러 개여도 선택한 서버의 번호나 선택 방법의 수는 출력하지 않는다. 입력에 나열된 서버의 순서는 선택 우선순위를 뜻하지 않는다. K가 N이면 모든 서버를 선택해야 하며, 선택한 서버의 작업 수가 모두 0이면 정답도 0이다. 항상 선택 가능한 수의 서버가 주어지므로 선택할 서버가 부족한 경우는 없다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000이며 1 ≤ K ≤ N이다.
둘째 줄에 각 서버의 작업 수를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 100,000이다.

출력

정확히 K대를 선택했을 때 가능한 작업 수 합의 최솟값을 정수 하나로 출력한다.

6 3
12 4 9 4 0 15

8

4 4
7 0 7 2

16

5 2
0 8 0 0 3

0

출처: Devin.KR 자체 제작