import sys
from collections import deque

def main():
    n, K, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    s = [0] * (n + 1)
    for i in range(1, n + 1):
        s[i] = s[i-1] + A[i-1]
    
    prev = [-float('inf')] * (n + 1)
    prev[0] = 0
    
    for k in range(1, K + 1):
        current = [-float('inf')] * (n + 1)
        q1 = deque()  # Maintains max(prev[j] - s[j])
        q2 = deque()  # Maintains max(prev[j] + s[j])
        max_i = min(k * M, n)
        for i in range(k, max_i + 1):
            j = i - 1
            if prev[j] != -float('inf'):
                val1 = prev[j] - s[j]
                while q1 and (prev[q1[-1]] - s[q1[-1]] <= val1):
                    q1.pop()
                q1.append(j)
                val2 = prev[j] + s[j]
                while q2 and (prev[q2[-1]] + s[q2[-1]] <= val2):
                    q2.pop()
                q2.append(j)
            L = max(k-1, i - M)
            while q1 and q1[0] < L:
                q1.popleft()
            while q2 and q2[0] < L:
                q2.popleft()
            
            current_val = -float('inf')
            if q1:
                current_val = max(current_val, (prev[q1[0]] - s[q1[0]]) + s[i])
            if q2:
                current_val = max(current_val, (prev[q2[0]] + s[q2[0]]) - s[i])
            if current_val != -float('inf'):
                current[i] = current_val
        prev = current
    
    print(prev[n])

if __name__ == "__main__":
    main()