Gift Packaging by Cows

Farmer John wants to maximize the total skill level of his cows when packaging gifts. He has N cows (numbered 1 through N) lined up, where the i-th cow has a packaging skill level s_i. He plans to divide the cows into contiguous groups, with each group containing at most K cows. In each group, every cow’s skill level becomes equal to the maximum skill level within that group. Your task is to determine the maximum possible sum of skill levels after grouping optimally.

Constraints:

• 1 ≤ N ≤ 10⁴
• 1 ≤ K ≤ 10³

The optimal solution can be obtained by using dynamic programming. For each starting index i, consider grouping cows from i to min(N, i+K-1) and updating the overall maximum sum accordingly. In mathematical terms, if we define dp[i] as the maximum sum obtainable from cow i to cow N, then:

[ \text{dp}[i] = \max_{i \le j \le \min(N, i+K-1)} \left{ (j-i+1) \times \max_{i \le k \le j}{s_k} + \text{dp}[j+1] \right} ]

Compute dp[0] (or dp[1] if using 1-indexing) to get the answer.

inputFormat

The first line contains two integers N and K separated by a space.

The second line contains N space-separated integers, representing the skill levels s₁, s₂, ..., s_N of the cows.

outputFormat

Output a single integer which is the maximum total skill level achievable after optimally grouping the cows.

sample

5 3
1 15 7 9 2

63