팀워크

면접 대비

시간 제한2초메모리 제한512 MB

요약

K마리 이하의 연속한 소로 한 팀을 이뤄 팀당 최대 실력으로 값을 합산할 때, 그 합을 최대로 만들 분할을 찾습니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

농부 존은 가장 좋아하는 명절을 맞아 친구들에게 선물을 보내려고 한다. 그런데 선물 포장을 잘하지 못해서 소들의 도움을 받기로 했다. 짐작하겠지만 소들도 선물 포장을 잘하지 못한다. 농부 존은 이 사실을 곧 뼈저리게 깨닫게 된다.

농부 존의 소 $N$ 마리( $1 \leq N \leq 10^4$ )가 한 줄로 서 있고, 순서대로 $1 \ldots N$ 번이 붙어 있다. 소 $i$ 의 선물 포장 실력은 $s\_i$ 이다. 실력 차이가 꽤 클 수 있기 때문에 FJ는 소들을 팀으로 묶기로 했다. 팀은 연속한 소 최대 $K$ 마리로 구성할 수 있으며( $1 \leq K \leq 10^3$ ), 한 소가 둘 이상의 팀에 속할 수는 없다. 소들은 서로에게 배우므로, 팀에 속한 각 소의 실력은 그 팀에서 가장 실력이 좋은 소의 실력으로 바뀔 수 있다.

FJ가 팀을 적절히 구성해서 얻을 수 있는 실력 합의 최댓값을 구해 주자.

입력

첫째 줄에 $N$ 과 $K$ 가 주어진다. 다음 $N$ 개 줄에 소들이 서 있는 순서대로 $N$ 마리의 실력이 주어진다. 각 실력은 $10^5$ 이하인 양의 정수이다.

출력

FJ가 연속한 소들을 적절히 팀으로 묶어서 얻을 수 있는 실력 합의 최댓값을 출력한다.

힌트

이 예에서 최적해는 처음 세 마리와 마지막 세 마리를 묶고, 가운데 소는 혼자 한 팀으로 두는 것이다(팀의 크기가 $K$ 보다 작아도 된다는 점을 기억하자). 그러면 7마리의 실력이 15, 15, 15, 9, 10, 10, 10이 되고, 합은 84이다.

예제1

예제 1
입력
```
7 3
1
15
7
9
2
5
10
```
예상 출력
```
84
```