짧은 무대 점검 묶음

문제

공연장에서는 개장 전에 여러 공연의 무대 장치를 점검한다. 오늘 점검할 수 있는 후보 공연은 N개이며, 각 공연의 장치를 점검하는 데 필요한 시간이 미리 정해져 있다. 운영 담당자는 이 중 정확히 K개의 공연을 골라 하나의 점검 묶음으로 진행하려 한다. 모든 후보를 반드시 점검할 필요는 없지만, 정해진 개수인 K개는 반드시 선택해야 한다. 한 공연의 점검을 시작하면 정해진 시간 동안 중단 없이 진행한다. 선택한 공연들의 점검은 한 번에 하나씩 이어서 진행하며, 서로 겹쳐 진행할 수 없다. 같은 공연을 두 번 선택할 수도 없다. 선택하지 않은 공연은 이번 점검 묶음에 포함되지 않으며, 그 공연의 점검 시간은 묶음의 소요 시간에 영향을 주지 않는다. 서로 이웃한 두 점검 사이에는 장치 교체를 위한 시간이 정확히 5분 필요하다. 이 교체 시간은 어떤 공연을 선택했는지, 어떤 순서로 점검하는지와 관계없이 같다. 첫 번째 점검을 시작하기 전과 마지막 점검을 마친 뒤에는 추가 시간이 들지 않는다. 따라서 공연을 하나만 선택하면 교체 시간이 없고, 공연을 하나도 선택하지 않으면 점검 묶음의 소요 시간은 0분이다. 운영 담당자는 점검 묶음이 가능한 한 빨리 끝나기를 원한다. 묶음의 소요 시간은 선택한 공연들의 점검 시간 합과 점검 사이의 모든 교체 시간을 더한 값이다. 공연별 점검 시간이 주어졌을 때, 정확히 K개를 선택하여 만들 수 있는 가장 짧은 소요 시간을 구해야 한다. 점검 시간이 같은 공연도 서로 다른 후보로 취급한다. 최소 시간을 만드는 선택이 여러 개여도 어떤 공연을 선택했는지나 점검 순서를 출력할 필요는 없다. 모든 시간은 분 단위 정수이며, 이동 시간이나 다른 준비 시간은 별도로 고려하지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)
둘째 줄에 각 공연의 점검 시간 T₁, T₂, …, Tₙ이 공백으로 구분되어 주어진다. 모든 Tᵢ는 정수이다. (1 ≤ Tᵢ ≤ 1,000)

출력

정확히 K개의 공연을 선택했을 때 점검 묶음의 최소 소요 시간을 분 단위 정수로 출력한다. K가 0이면 0을 출력한다.

5 3
12 4 9 4 20

27

4 0
7 7 2 10

0

3 3
6 1 8

25

출처: Devin.KR 자체 제작