Nap Time

Donghyuk divides his nap time into N intervals and wants to sleep during exactly B of them. The chosen B intervals do not have to be consecutive.

Each interval has a fixed amount of fatigue recovery. However, Donghyuk needs preparation time before falling asleep, so in each consecutive block of chosen intervals, the first interval gives no recovery. For instance, if intervals [2 3 4] are chosen, interval [2] gives no recovery and only intervals [3 4] contribute their recovery amounts.

Interval N and interval 1 are not considered adjacent.

Find the maximum total fatigue recovery Donghyuk can obtain by choosing exactly B intervals.

The first line contains two integers N and B.

N is between 3 and 3,000, inclusive, and B is between 2 and N, inclusive.

Each of the next N lines contains the fatigue recovery amount for one interval. Each value is an integer between 0 and 200,000, inclusive.

Print the maximum possible fatigue recovery on the first line.

For the provided visible test data, choosing intervals [1] and [4 5] gives 0 + 0 + 2, because the first interval of each consecutive block gives no recovery.

Choosing intervals [3 4 5] gives 0 + 4 + 2, so the maximum is 6.