Non-Consecutive Tree Picking

You are given N trees in a row with given heights. Your task is to choose exactly K trees such that no two chosen trees are consecutive. Formally, if you select trees at indices i₁, i₂, ..., i_K (using 1-indexing), then for every j from 1 to K-1, it must hold that i_j+1 - i_j > 1.

Your goal is to maximize the sum of the heights of the selected trees. If it is not possible to choose K trees under these conditions, output -1.

In mathematical terms, you want to maximize:

[ S = \sum_{i \in S} \text{heights}[i] \quad \text{subject to} \quad |S| = K \text{ and } \forall i, j \in S,; |i - j| \neq 1. ]

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains two integers N and K separated by a space, where N is the number of trees and K is the number of trees to pick.
2. The second line contains N integers, representing the heights of the trees from left to right.

outputFormat

Output a single integer to standard output (stdout): the maximum sum of the heights of the K picked trees such that no two are consecutive. If it is not possible to pick K trees under the given conditions, output -1.

7 3
10 20 30 40 50 60 70

150