Divide Intervals

You are given a one-dimensional array of N integers, where 1 <= N <= 100. Choose exactly M intervals from the array, where 1 <= M <= ceil(N / 2), so that the total sum of all numbers contained in the chosen intervals is as large as possible.

The chosen intervals must satisfy all of the following conditions.

1. Each interval consists of one or more consecutive numbers.
2. No two different intervals may overlap or be adjacent to each other.
3. Exactly M intervals must be chosen; choosing fewer than M intervals is not allowed.

Given the N integers, compute the maximum possible total sum.

The first line contains two integers N and M.

Each of the next N lines contains one integer from the array, in order. Every array value is an integer between -32768 and 32767, inclusive.

Print one integer: the maximum possible total sum of the numbers contained in the chosen intervals.