Morning Run Optimization

Betsey the cow wants to maximize her running distance during a morning exercise routine of n minutes. At the start of each minute, she must decide whether to run or rest. If she chooses to run in the i-th minute, she runs a distance of \(d_i\) meters and her fatigue increases by 1; however, her fatigue must never exceed \(m\). On the other hand, if she chooses to rest then her fatigue decreases by 1 per minute. There is an important twist: if her fatigue is greater than 0 and she decides to rest, she must continue resting consecutively until her fatigue is fully recovered to 0. (Note that if her fatigue is already 0, a rest minute keeps it 0.)

Additionally, at the end of the n minutes her fatigue must be 0. Otherwise, she won’t have enough energy for the rest of the day. Compute the maximum distance she can run under these conditions.

The process can be summarized as follows:

• If Betsey runs in the i-th minute with current fatigue \(f\) such that \(f < m\), then her fatigue becomes \(f+1\) and she covers \(d_i\) meters.
• If she rests when her fatigue is 0, nothing changes.
• If she rests when her fatigue is \(f>0\), then she must continue resting in the following minutes until her fatigue reduces to 0. In that resting block, each minute reduces her fatigue by 1.
• The final state after n minutes must have a fatigue of 0.

Input Constraints:

• \(1 \leq n \leq 10^5\) (number of minutes)
• \(0 \leq m \leq n\) (maximum allowable fatigue)
• \(d_i\) are positive integers representing the running distance in each minute.

Hint: Dynamic programming is a good approach. Define a state \(dp(i, f)\) as the maximum distance achievable starting from minute \(i\) with current fatigue \(f\) when a free decision can be made. The transitions account for choosing to run or to rest (with forced consecutive resting if fatigue > 0). When running, the state transitions to \(dp(i+1, f+1)\) (provided \(f 0\) a forced block of \(f\) minutes occurs, transitioning to \(dp(i+f, 0)\) (this option is only valid if \(i+f \le n\)).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of minutes and \(m\) is the maximum fatigue allowed. The second line contains \(n\) integers \(d_1, d_2, \ldots, d_n\), where \(d_i\) represents the distance (in meters) that Betsey can run in the \(i\)-th minute if she chooses to run.

outputFormat

Output a single integer representing the maximum distance (in meters) that Betsey can run while meeting the fatigue constraints.

sample

5 2
5 3 4 2 10

18