시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 25 9 9 69.231%

문제

동혁이는 낮잠 시간을 N개의 구간으로 나누어서 그 중 B개의 구간동안만 잠을 자려고 한다. B개의 구간이 연속일 필요는 없다. 각 구간동안에 동혁이가 얻을 수 있는 피로 회복량이 정해져 있는데, 동혁이는 이 양을 최대화 하려고 한다. 잠을 설치는 경우가 한 예이다.

예를 들어 구간을 5개로 나누었을 경우, B=3이고 [2 3 4]구간에 잠을 자기로 했다고 치자. 잠을 들기 위해서는 준비 시간이 필요하기 때문에 이 준비 시간 동안에는 피로 회복이 되지 않는다. 각 분할의 첫 구간에서는 피로가 회복되지 않는 것이다. 따라서 [2 3 4] 구간에 잠을 자면 [2]구간에서는 회복을 못하고 [3 4]구간에서만 회복할 수 있다. 이 구간은 N번째 구간과 1번째 구간이 이어져있지 않다고 생각하자.

동혁이가 어떻게 하면 피로회복을 최대로 할 수 있는지 구해보자.

입력

 첫 줄에 N과 B가 주어진다. N은 3이상 3,000이하이고 B는 2이상 N미만이다. 다음으로 N줄에 걸쳐 피로회복량이 주어지는 0이상 200,000 이하의 자연수이다.

출력

 첫 줄에 가능한 최대 피로회복량을 출력한다.

예제 입력

5 3
0
3
1
4
2

예제 출력

6

힌트

  가령 [1] [4 5]와 같이 선택한다면 0 + 0 + 2 가 된다. (구간을 여러 분할하면 여러 분할의 각 첫 구간은 피로 회복을 할 수 없다) 위의 예에서는 [3 5]구간을 선택하면 0 + 4 + 2 가 되어 최대가 된다.