Description

cyrcyr is planting trees today. He dug $n$ pits on a straight line. Each of these $n$ pits can be used to plant a tree, but to ensure every tree has sufficient nutrients, cyrcyr will not plant trees in two adjacent pits. Also, because cyrcyr does not have enough saplings, he will plant at most $k$ trees. Assuming cyrcyr has a special ability to foresee the profit from planting a tree in any pit (which may be negative), please help him compute his maximum total profit.

Input Format

The first line contains two positive integers $n, k$.

The second line contains $n$ integers. The $i$-th number denotes the profit from planting a tree in the $i$-th pit from left to right on the line.

Output Format

Output a single number, the maximum profit that cyrcyr can obtain.

6 3 
100 1 -1 100 1 -1

200

Hint

For $20\%$ of the testdata, $n \leq 20$.

For $50\%$ of the testdata, $n \leq 6000$.

For $100\%$ of the testdata, $1 \le n \le 300000$, $1 \le k \le \dfrac{n}{2}$, and the absolute value of the profit at any single position is at most $10^6$.

Translated by ChatGPT 5