Maximizing Tree Planting Profit

cyrcyr dug \(n\) pits along a straight line. Each pit has an associated profit value for planting a tree, which may be negative. However, to ensure that every tree receives enough nutrients, cyrcyr will not plant trees in two adjacent pits. Moreover, because the number of trees he possesses is limited, he will plant at most \(k\) trees.

Formally, given an array \(a\) of length \(n\), select a subset of indices such that no two selected indices are consecutive and the number of selected indices does not exceed \(k\). The objective is to maximize the total profit:

[ \max \sum_{i \in S} a_i ]

where \(S\) is any subset of \(\{1, 2, \dots, n\}\) satisfying:

[ \text{if } i \in S \text{ then } i+1 \notin S, \quad \text{and } |S| \le k. ]

</p>

You may choose to plant fewer than \(k\) trees (including not planting any tree) if it leads to a higher profit.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(k\), representing the number of pits and the maximum number of trees that can be planted.
• The second line contains \(n\) integers, where the \(i\)-th integer represents the profit for planting a tree in the \(i\)-th pit.

outputFormat

Output a single integer representing the maximum profit that can be achieved under the given constraints.

sample

5 2
1 2 3 4 5

8

</p>