def main(): import sys from collections import deque N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) prefix = [0] * (N + 1) for i in range(N): prefix[i+1] = prefix[i] + A[i] dp_not = [0] * (N+1) # dp_not[i]: max sum up to i-1, not taking i-1 taken = [0] * (N+1) max_taken_prev = 0 q = deque() q.append(-1) S = prefix for i in range(N): current_i = i j_start = current_i - K + 1 while q and q[0] < j_start: q.popleft() if q: best = dp_not[q[0] + 1] - S[q[0] + 1] else: best = -float('inf') # Compute taken_val if j_start <= -1: best = max(best, 0 - S[0]) # j = -1, which is allowed taken_val = best + S[i+1] taken[i+1] = taken_val # Update dp_not[i+1] new_dp_not = max(dp_not[i], max_taken_prev) dp_not[i+1] = new_dp_not # Update the deque with j = i current_H = new_dp_not - S[i+1] while q and (dp_not[q[-1]+1] - S[q[-1]+1] <= current_H): q.pop() q.append(i) max_taken_prev = taken_val print(max(dp_not[N], taken[N])) if __name__ == "__main__": main()