**PROBLEM LINK:**

link:Contest

Author: @kostya_by

Tester: @white_king

**DIFFICULTY:**

Easy

**PROBLEM:**

This can be solved using dynamic programming.

Call best_forward* to be the maximum prosperity of a sequence that ends at i. This can be computed as:

best_forward*=max(A*, best_forward[i-1] + A*).

From this, you may easily compute the maximum prosperity of any sequence that ends anywhere between 0…i as:

cumulative_best_forward* = max(cumulative_best_forward[i-1], best_forward*).

Similarly let best_backward* be the maximum prosperity of a sequence starting at i

best_backward*=max((ll)A*, best_backward[i+1] + A*). Similarly, you compute cumulative_best_backward*.

The answer is simply

max_{j=K+2 to N} (cumulative_best_forward[j-K-1] + cumulative_best_backward[j]).