그림 구매

크리에이티브 커먼즈 저작자표시-동일조건변경허락

Mona는 막 이사했고 이제 집을 꾸미기 시작하려 한다. Mona는 그림이 정확히 $k$점 필요하다는 결론을 내리고, 그림을 사기 위해 미술 시장에 갔다. Mona는 매우 부유해서 그림 가격에는 전혀 신경 쓰지 않고, 그저 가능한 한 빨리 구매를 마치고 싶어 한다.

시장에서는 긴 거리를 따라 $N$점의 그림을 판매한다. 그림 $i$을 구매하는 데에는 $t_i$초가 걸린다. 한 그림에서 다음 그림으로 걸어가는 데에는 1초가 걸린다. Mona는 그곳에 갈 때와 돌아올 때 버스를 타므로, 어느 그림에서 시작하고 끝낼지 선택할 수 있다. Mona가 $k$점의 그림을 구매하는 데 걸리는 가장 짧은 시간은 얼마인가?

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$7$| $k=1$

$2$ |$10$| $k=2$

$3$ |$30$| $N \le 200$

$4$ |$53$| 추가 제한 없음.

첫 번째 줄에는 두 정수, 즉 시장에 있는 그림의 수 $N$ ($1 \le N \le 2000$)와 Mona가 구매해야 하는 그림의 수 $k$ ($1 \le k \le N$)가 주어진다.

두 번째 줄에는 각 그림을 구매하는 데 걸리는 시간(초)을 나타내는 $N$개의 정수 $1 \le t_1,t_2,...t_n \le 1000$가 주어진다.

Mona가 $k$점의 그림을 구매하는 데 걸릴 수 있는 최소 시간(초)을 정수로 출력한다.