구간 나누기

N개의 정수로 이루어진 1차원 배열이 있다. 여기서 1 <= N <= 100이다. 이 배열에서 정확히 M개의 구간을 골라, 선택한 구간 안에 포함된 모든 수의 합이 최대가 되게 하려고 한다. 여기서 1 <= M <= ceil(N / 2)이다.

선택한 구간은 다음 조건을 모두 만족해야 한다.

1. 각 구간은 하나 이상의 연속된 수로 이루어진다.
2. 서로 다른 두 구간은 겹치거나 서로 인접하면 안 된다.
3. 반드시 정확히 M개의 구간을 선택해야 하며, M개보다 적게 선택할 수 없다.

배열의 N개 수가 주어졌을 때, 만들 수 있는 최대 합을 구하시오.

첫째 줄에 두 정수 N과 M이 주어진다.

다음 N개의 줄에는 배열을 이루는 정수가 순서대로 하나씩 주어진다. 각 수는 -32768 이상 32767 이하의 정수이다.

선택한 구간에 포함된 수들의 총합으로 만들 수 있는 최댓값을 한 줄에 출력한다.