A drone flies over n survey cells in order; cell i yields an energy reading a[i] (possibly negative). The drone samples a subsequence of the cells: it may skip cells, but any two consecutively sampled cells must be at most k indices apart. At least one cell must be sampled.
Report the maximum possible total energy of a valid sampled subsequence.
Formally, choose indices i_1 < i_2 < ... < i_m (with m >= 1) such that i_{t+1} - i_t <= k for every consecutive pair, maximizing a[i_1] + a[i_2] + ... + a[i_m].
Input format
Line 1: two integers n and k.
Line 2: n space-separated integers, the energy readings a[0..n-1].
Output format
A single integer: the maximum total energy of a valid non-empty subsequence.
Constraints
- 1 <= k <= n <= 100000
- -1000000000 <= a[i] <= 1000000000