창구의 서류 묶음 준비

문제

은행 창구의 직원은 다음 날 방문할 예약 고객을 위해 안내 서류 묶음을 준비한다. 예약 고객은 모두 N명이며, 고객마다 필요한 안내 서류의 장수가 정해져 있다. 어떤 고객에게 필요한 서류가 여러 장이라면 그 고객의 서류를 전부 준비해야 하나의 묶음이 완성된다. 일부 장만 준비한 묶음은 완성한 것으로 세지 않는다. 직원은 오늘 정확히 K명의 서류 묶음을 완성하려고 한다. 나머지 고객의 서류는 다음 근무 시간에 준비할 예정이며, 오늘 선택하지 않았다고 해서 예약이 취소되거나 다른 불이익이 생기지는 않는다. 모든 고객은 오늘 준비할 대상으로 자유롭게 선택할 수 있다. 고객별 우선순위나 반드시 함께 선택해야 하는 조건은 없다. 오늘 사용할 종이를 아끼기 위해, 직원은 선택한 K명의 서류 장수 합계가 가장 작아지도록 고객을 고르려고 한다. 한 장의 종이는 한 고객의 서류에만 사용할 수 있다. 서로 다른 고객에게 같은 내용의 안내가 필요하더라도 종이를 공유하거나 한 장으로 합칠 수 없다. 준비 과정에서 버리는 종이는 없으므로 오늘 사용하는 종이의 총장수는 선택한 고객들의 필요 장수를 더한 값과 같다. 입력에는 고객별 필요 장수가 예약 접수 순서대로 주어진다. 접수 순서는 선택에 영향을 주지 않으며, 필요한 장수가 같은 고객이 여러 명 있어도 각각 다른 고객으로 취급한다. 최소 합계를 만드는 선택이 여러 가지라면 어느 선택을 사용해도 된다. 출력에는 고객의 번호나 준비 순서가 아니라 최소 합계만 필요하므로 동점인 고객 사이의 별도 우선순위는 없다. 오늘 준비할 묶음이 없는 K=0인 경우도 있다. 이 경우에는 어떤 고객도 고르지 않으며 사용하는 종이는 0장이다. K는 전체 고객 수를 넘지 않으므로 그 밖의 경우에는 항상 정확히 K명을 고를 수 있다. 주어진 필요 장수를 이용하여 오늘 사용할 종이의 최소 총장수를 구해야 한다.

입력

첫째 줄에 고객 수 N과 오늘 준비할 묶음 수 K가 공백으로 구분되어 주어진다. 두 값은 정수이며 1 ≤ N ≤ 1,000, 0 ≤ K ≤ N이다.
둘째 줄에 각 고객의 필요 장수를 나타내는 N개의 정수가 접수 순서대로 주어진다. 각 값은 1 이상 1,000 이하이다.

출력

정확히 K명의 서류 묶음을 준비할 때 사용하는 종이의 최소 총장수를 정수 하나로 출력한다. K가 0이면 0을 출력한다.

6 3
8 3 6 3 10 5

11

4 0
7 2 9 2

0

3 3
4 4 1

9

출처: Devin.KR 자체 제작