낮잠 시간

동혁이는 낮잠 시간을 N개의 구간으로 나누고, 그중 정확히 B개의 구간에서 잠을 자려고 한다. 선택한 B개의 구간이 서로 연속일 필요는 없다.

각 구간에는 그 구간에서 얻을 수 있는 피로 회복량이 정해져 있다. 다만 잠을 시작할 때는 준비 시간이 필요하므로, 선택한 구간들이 하나의 연속된 묶음을 이룰 때 그 묶음의 첫 구간에서는 피로가 회복되지 않는다. 예를 들어 [2 3 4]번 구간을 선택하면 [2]번 구간에서는 회복하지 못하고 [3 4]번 구간의 회복량만 얻는다.

N번째 구간과 1번째 구간은 서로 이어져 있지 않다고 본다.

정확히 B개의 구간을 골랐을 때 얻을 수 있는 피로 회복량의 최댓값을 구하라.

첫 줄에 두 정수 N과 B가 주어진다.

N은 3 이상 3,000 이하이고, B는 2 이상 N 이하이다.

다음 N줄에는 각 구간의 피로 회복량이 한 줄에 하나씩 주어진다. 각 값은 0 이상 200,000 이하의 정수이다.

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

입력으로 주어진 값에서 [1], [4 5]번 구간을 선택하면 각 연속 묶음의 첫 구간은 회복되지 않으므로 0 + 0 + 2를 얻는다.

[3 4 5]번 구간을 선택하면 0 + 4 + 2를 얻어 최댓값 6이 된다.