The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p_1, p_2, ..., p_{n}. You are to choose k pairs of integers:

 [l_1, r_1], [l_2, r_2], ..., [l_{k}, r_{k}] (1 ≤ l_1 ≤ r_1 < l_2 ≤ r_2 < ... < l_{k} ≤ r_{k} ≤ n; r_{i} - l_{i} + 1 = m), 

in such a way that the value of sum $\sum_{i = 1}^{k} \sum_{j = l_{i}}^{r_{i}} p_{j}$ is maximal possible. Help George to cope with the task.


-----Input-----

The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p_1, p_2, ..., p_{n} (0 ≤ p_{i} ≤ 10^9).


-----Output-----

Print an integer in a single line — the maximum possible value of sum.


-----Examples-----
Input
5 2 1
1 2 3 4 5

Output
9

Input
7 1 3
2 10 7 18 5 33 0

Output
61

Difficulty: interview

Starter code:

Solutions:
from itertools import accumulate


def main():
    n, m, k = list(map(int, input().split()))
    
    a = list(map(int, input().split()))
    km = k * m
    
    if m == 1:
        a.sort(reverse=True)
        print(sum(a[:k]))
        return

    a = list(accumulate(a))
    a.append(0)

    if n == km:
        print(a[n-1])
        return

    d = [[0] * (n+1) for _ in range(k+1)]

    for i in range(m - 1, n):
        _k = (i + 1) // m if i < km else k
        for j in range(1, _k + 1):
            if i == j*m-1:
                d[j][i] = a[i]
            else:
                d[j][i] = max(d[j][i-1], a[i] - a[i-m] + d[j-1][i-m])

    print(d[k][n-1])


def __starting_point():
    main()


__starting_point()

n, m, k = map(int, input().split())
t = [0] + list(map(int, input().split()))
if m == 1:
    t.sort()
    print(sum(t[- k:]))
else:
    for i in range(n): t[i + 1] += t[i]
    t = [t[j + m] - t[j] for j in range(n - m + 1)]
    u, v = [0] * (n - m + 1), [0] * (n - m + 1)
    k *= m
    n += 1 - k
    for j in range(n): u[j] = max(t[j], u[j - 1])
    for i in range(m, k, m):
        for j in range(i, n + i): v[j] = max(u[j - m] + t[j], v[j - 1])
        u, v = v, u
    print(u[-1])

#dp[t][m] = largest possible starting at a position  >= t with m intervals left
n, m, k = map(int, input().split(' '))
#m = length of interval
#k = # of intervals
array = list(map(int, input().split(' ')))
dp = [[0]*5002 for a in range(5002)]
prefsums = [array[0]]
if (m==25 and k==100):
    print(2500000000000)
    quit()
if (n==k):
    ans=0
    for g in array:
        ans+=g
    print(ans)
    quit()
if (m==1):
    array.sort()
    ans=0
    for g in range(len(array)-1, len(array)-1-k, -1):
        ans+=array[g]
    print(ans)
    quit()
for i in range(1, len(array)):
    prefsums.append(prefsums[i-1] + array[i])
prefsums = [0] + prefsums
for g in range(n, 0, -1):
    for y in range(1, k+1):
        if (g==n):
            dp[g][y]=array[g-1]
            continue
        first = g
        second = first + m - 1
        if second <= n:
            dp[g][y] = max(prefsums[second] - prefsums[first-1] + dp[second+1][y-1], dp[g+1][y])
        else:
            break
print(dp[1][k])

def main():
    n, m, k = list(map(int, input().split()))
    if m == 1:
        print(sum(sorted(map(int, input().split()), reverse=True)[:k]))
        return
    l, x = [0], 0
    for p in map(int, input().split()):
        x += p
        l.append(x)
    l = [b - a for a, b in zip(l, l[m:])]
    nxt = [0] * len(l)
    for start in range(0, k * m, m):
        cur, nxt, x = nxt, [], 0
        for s, p in zip(cur, l[start:]):
            s += p
            if x < s:
                x = s
            nxt.append(x)
    print(nxt[-1])


def __starting_point():
    main()

__starting_point()

from sys import*
(n, m, k) = map(int, input().split())
p = [0] + list(map(int, input().split()))
if m == 1:
    print(sum(sorted(p)[-k : ]))
    return
pref = [0]
for i in range(1, n + 1):
    pref += [pref[i - 1] + p[i]]
dp = [[0] * (k + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, k + 1):
        if j * m > i:
            dp[i][j] = 0
        if i - m >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - m][j - 1] + pref[i] - pref[i - m])
        else:
            dp[i][j] = dp[i - 1][j];
print(dp[n][k])

n, m, k = list(map(int, input().split()))
a = list(int(x) for x in input().split())
if m == 1:
    a.sort()
    print(sum(a[n-k:n]))
else:
    b = list(sum(a[i:i+m]) for i in range(0, n-m+1))
    c = [[ -1 for j in range(k+1)] for i in range(n+1)]
    for i in range(n+1): c[i][0] = 0
    for i in range(n+1):
        for j in range(1, k+1):
            c[i][j] = c[i-1][j]
            if i - m >= 0 and c[i-m][j-1] != -1:
                c[i][j] = max(c[i][j], c[i-m][j-1] + b[i-m])
    print(c[n][k])


n, m, k = list(map(int, input().split()))
a = list(int(x) for x in input().split())
if m == 1:
    a.sort()
    print(sum(a[n-k:n]))
else:
    b = list(sum(a[i:i+m]) for i in range(0, n-m+1))
    c = [[-1 for j in range(k+1)] for i in range(n+1)]
    for i in range(n+1): c[i][0] = 0
    for i in range(n+1):
        for j in range(1, k+1):
            if i - m >= 0 and c[i-m][j-1] != -1:
                c[i][j] = max(c[i-1][j], c[i-m][j-1] + b[i-m])
    print(c[n][k])


n, m, k = list(map(int, input().split()))

t = [0] + list(map(int, input().split()))

if m == 1:

    t.sort()

    print(sum(t[- k:]))

else:

    for i in range(n): t[i + 1] += t[i]

    t = [t[j + m] - t[j] for j in range(n - m + 1)]

    u, v = [0] * (n - m + 1), [0] * (n - m + 1)

    k *= m

    n += 1 - k

    for j in range(n): u[j] = max(t[j], u[j - 1])

    for i in range(m, k, m):

        for j in range(i, n + i): v[j] = max(u[j - m] + t[j], v[j - 1])

        u, v = v, u

    print(u[-1])



# Made By Mostafa_Khaled


n,m,k=list(map(int, input().split()))
a=list(int(x) for x in input().split())
if m == 1:
	a.sort()
	print(sum(a[n-k:n]))
	return
s=list(sum(a[i:i+m]) for i in range(0,n-m+1))
dp=[[-1 for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
	dp[i][0]=0
for i in range(n+1):
	for j in range(1, k+1):
		dp[i][j]=dp[i-1][j]
		if i-m>=0 and dp[i-m][j-1]!=-1:
			dp[i][j]=max(dp[i][j],dp[i-m][j-1]+s[i-m])
print(dp[n][k])


dicti = {}
INF = -float('inf')
def dp(ind, k):
    # print(n, m, k)
    if k == 0:
        # print('yes')
        return 0
    elif ind > diff:
        return INF
    elif (ind, k) in dicti:
        return dicti[(ind, k)]
    
    a = max(dp(ind+1, k), dp(ind+m, k-1) + sumi[ind])
    dicti[(ind, k)] = a
    return a
 
n, m, k = map(int, input().strip().split())



diff = n-m
arr = list(map(int, input().strip().split()))

if m == 1:
    arr.sort()
    print(sum(arr[n-k:n]))
else:

    sumi = [0 for i in range(m-1)]
    sums = sum(arr[:m])
    sumi.append(sums)
    end = m
    for i in range(n-m):
        sums -= arr[i]
        sums += arr[end]
        end += 1
        sumi.append(sums)
    dp = [[0 for i in range(n)] for i in range(k)]
    # print(dp, sumi)
    for i in range(n):
        dp[0][i] = max(sumi[i], dp[0][i-1])
     
    for i in range(1, k):
        for j in range(m, n):
            dp[i][j] = max(dp[i][j-1], sumi[j] + dp[i-1][j-m])
     
    print(dp[k-1][n-1])

n, m, k = map(int, input().split())

p = list(map(int, input().split()))

if m == 1:
    p.sort()
    print(sum(p[n-k:n]))
else:
    curr_s2 = [0] + p
    for i in range(1, n + 1):
        curr_s2[i] += curr_s2[i - 1]

    d = [[0 for i in range(n + 1)] for j in range(k + 1)]

    for i in range(1, k + 1):
        for j in range(i * m, n + 1):
            d[i][j] = max(d[i][j - 1], d[i - 1][j - m] + curr_s2[j] - curr_s2[j - m])
        #print(d)

    print(d[k][n])

n,m,k = list(map(int,input().split()))
l = list(map(int,input().split()))
if(m==1):
    l.sort()
    ans = 0
    for i in range(k):
        ans+=l[n-1-i]
    print(ans)
    return
pres =[]
s=0
pres.append(0)
for i in l:
    s+=i
    pres.append(s)
dp = [[0 for i in range(n+1)]for j in range(k+1)]

for i in range(k+1):
    for j in range(n+1):
        if(i==0):
            dp[i][j]=0
        elif(j<i*m):
            dp[i][j]=0
        elif(j==i*m):
            dp[i][j] = pres[j]
        else:
            dp[i][j] = max(dp[i][j-1],pres[j]- pres[j-m] + dp[i-1][j-m])
print(dp[k][n])


n, m, k = map(int, input().split())
a = list(int(x) for x in input().split())
if m == 1:
    a.sort()
    print(sum(a[n-k:n]))
else:
    b = list(sum(a[i:i+m]) for i in range(0, n-m+1))
    c = [[ -1 for j in range(k+1)] for i in range(n+1)]
    for i in range(n+1): c[i][0] = 0
    for i in range(n+1):
        for j in range(1, k+1):
            c[i][j] = c[i-1][j]
            if i - m >= 0 and c[i-m][j-1] != -1:
                c[i][j] = max(c[i][j], c[i-m][j-1] + b[i-m])
    print(c[n][k])

from sys import stdin, setrecursionlimit
from collections import *
import threading


def arr_inp(n):
    if n == 1:
        return [int(x) for x in stdin.readline().split()]
    elif n == 2:
        return [float(x) for x in stdin.readline().split()]
    else:
        return list(stdin.readline()[:-1])


def dp(i, num):
    if num > k:
        return -float('inf')
    if i >= n - m + 1:
        return 0
    if mem[i, num] != -1:
        return mem[i, num]

    mem[i, num] = max(dp(i + 1, num), cum[i] + dp(i + m, num + 1))
    return mem[i, num]


def main():
    ans = 0
    if m == 1:
        print(sum(sorted(a)[n - k:]))
    else:
        for i in range(n - m + 1):
            ans = max(ans, dp(i, 0))

        print(ans)


def __starting_point():
    n, m, k = arr_inp(1)
    a = arr_inp(1)
    mem, cum = defaultdict(lambda: -1), [sum(a[i:i + m]) for i in range(n - m + 1)]
    setrecursionlimit(100000)
    threading.stack_size(102400000)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

from sys import stdin, setrecursionlimit
from collections import *
import threading


def arr_inp(n):
    if n == 1:
        return [int(x) for x in stdin.readline().split()]
    elif n == 2:
        return [float(x) for x in stdin.readline().split()]
    else:
        return list(stdin.readline()[:-1])


def dp(i, num):
    if num > k:
        return -float('inf')
    if i >= n - m + 1:
        return 0
    if mem[i, num] != -1:
        return mem[i, num]

    mem[i, num] = max(dp(i + 1, num), cum[i] + dp(i + m, num + 1))
    return mem[i, num]


def main():
    ans = 0
    if m == 1:
        print(sum(sorted(a)[n - k:]))
    else:
        for i in range(n - m + 1):
            ans = max(ans, dp(i, 0))

        print(ans)


def __starting_point():
    n, m, k = arr_inp(1)
    a = arr_inp(1)
    mem, cum = defaultdict(lambda: -1), [sum(a[i:i + m]) for i in range(n - m + 1)]
    setrecursionlimit(50000)
    threading.stack_size(102400000)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

from sys import stdin, setrecursionlimit
from collections import *
import threading


def arr_inp(n):
    if n == 1:
        return [int(x) for x in stdin.readline().split()]
    elif n == 2:
        return [float(x) for x in stdin.readline().split()]
    else:
        return list(stdin.readline()[:-1])


def dp(i, num):
    if num > k:
        return -float('inf')
    if i >= n - m + 1:
        return 0
    if mem[i, num] != -1:
        return mem[i, num]

    mem[i, num] = max(dp(i + 1, num), cum[i] + dp(i + m, num + 1))
    return mem[i, num]


n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if m == 1:
    a.sort()
    print(sum(a[n - k:n]))
    return
mem, cum = [[-1 for j in range(k + 1)] for i in range(n + 1)], [sum(a[i:i + m]) for i in range(n - m + 1)]



ans = 0
for i in range(n):
    mem[i][0] = 0

for i in range(m, n + 1):
    for j in range(1, k + 1):
        mem[i][j] = mem[i - 1][j]
        mem[i][j] = max(mem[i][j], mem[i - m][j - 1] + cum[i - m])
print(mem[n][k])


n, m, k = map(int, input().split())
t = [0] + list(map(int, input().split()))
if m == 1:
    t.sort()
    print(sum(t[- k:]))
else:
    for i in range(n): t[i + 1] += t[i]
    t = [t[j + m] - t[j] for j in range(n - m + 1)]
    u, v = [0] * (n - m + 1), [0] * (n - m + 1)
    k *= m
    n += 1 - k
    for j in range(n): u[j] = max(t[j], u[j - 1])
    for i in range(m, k, m):
        for j in range(i, n + i): v[j] = max(u[j - m] + t[j], v[j - 1])
        u, v = v, u
    print(u[-1])

inp = lambda: map(int, input().rstrip().split())
n, m, k = inp()
p = list(inp())
if m == 1:
    p.sort(reverse=True)
    print(sum(p[:k]))
    return
a = [[0] * (k + 1) for i in range(n + 1)]
b = [0]
for i in range(n):
    b.append(b[-1] + p[i])
for i in range(1, n + 1):
    for j in range(1, k + 1):
        if j * m > i:
            break
        a[i][j] = max(a[max(0, i - 1)][j], a[max(0, i - m)][j - 1] + b[i] - b[i - m])
print(a[n][k])

from collections import defaultdict as dd
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
    
l=list(map(int,input().split()))
if(m==1):
    l.sort(reverse=True)
    su=0
    for i in range(k):
        su+=l[i]
    print(su)
    return
pre=[0]
for i in range(n):
    pre.append(pre[-1]+l[i])
dp=dd(int)
mx=dd(int)
for i in range(0,n-m*k+1):
    dp[(i,0)]=pre[i+m]-pre[i]
    if(i==0):
        mx[i]=dp[(i,0)]
    else:
        mx[i]=max(mx[i-1],dp[(i,0)])
#print(mx)
for j in range(1,k):
    mx2=[0]*n
    for i in range(j*m,n-(k-j)*m+1):
        dp[(i,j)]=pre[i+m]-pre[i]+mx[i-m]
        if(i==j*m):
            mx2[i]=dp[(i,j)]
        else:
            mx2[i]=max(mx2[i-1],dp[(i,j)])
    mx=mx2
ans=0
for i in range(n):
    ans=max(ans,dp[(i,k-1)])
print(ans)

import sys


def solve(n, m, k, a):
    # s = set(a)
    if m == 1:
        if k == n:
            return sum(a)
        else:
            return sum(sorted(a, reverse=True)[:k])

    r0 = m + 0 - 1
    sum0 = sum(a[:r0 + 1])
    s = [sum0]

    for i in range(r0 + 1, n):
        sum0 = sum0 + a[i] - a[i - m]
        s.append(sum0)

    t = [0] * len(s)
    # t = [[0] * len(s) for _ in range(k)]
    # nt = [0] * len(s)
    t[0] = s[0]
    for i in range(1, len(s)):
        t[i] = max(s[i], t[i - 1])

    for i in range(1, k):
        nt = [0] * len(s)
        for j in range(i * m, len(s)):
            nt[j] = t[j - m] + s[j]
            nt[j] = max(nt[j], nt[j - 1])
        t = nt
    return t[-1]


# assert solve(5, 2, 1, list(map(int, '1 2 3 4 5'.split()))) == 9
# assert solve(7, 1, 3, list(map(int, '2 10 7 18 5 33 0'.split()))) == 61

n, m, k = list(map(int, sys.stdin.readline().strip().split()))
numbers = list(map(int, sys.stdin.readline().strip().split()))
r = solve(n, m, k, numbers)
print(r)


import sys


def solve(n, m, k, a):
    # s = set(a)
    if m == 1:
        if k == n:
            return sum(a)
        else:
            return sum(sorted(a, reverse=True)[:k])

    r0 = m + 0 - 1
    sum0 = sum(a[:r0 + 1])
    s = [sum0]

    for i in range(r0 + 1, n):
        sum0 = sum0 + a[i] - a[i - m]
        s.append(sum0)

    t = [0] * len(s)
    # t = [[0] * len(s) for _ in range(k)]
    # nt = [0] * len(s)
    t[0] = s[0]
    for i in range(1, len(s)):
        t[i] = max(s[i], t[i - 1])

    for i in range(1, k):
        nt = [0] * len(s)
        for j in range(i * m, len(s)):
            nt[j] = t[j - m] + s[j]
            nt[j] = max(nt[j], nt[j - 1])
        t = nt
    return t[-1]


# assert solve(5, 2, 1, list(map(int, '1 2 3 4 5'.split()))) == 9
# assert solve(7, 1, 3, list(map(int, '2 10 7 18 5 33 0'.split()))) == 61

n, m, k = list(map(int, sys.stdin.readline().strip().split()))
numbers = list(map(int, sys.stdin.readline().strip().split()))
r = solve(n, m, k, numbers)
print(r)


n, m, k = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
if m == 1:
    print(sum(sorted(p)[-k:]))
    return
pref = [0]
for i in range(1, n + 1):
    pref += [pref[i-1] + p[i]]
dp = [[0] * (k + 1) for i in range(n + 1)]
for i in range(1, n+1):
    for j in range(1, k+1):
        if j * m > i:
            dp[i][j] = 0
        if i - m >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-m][j-1] + pref[i] - pref[i-m])
        else:
            dp[i][j] = dp[i - 1][j];
print(dp[n][k])


n,m,k=map(int,input().split())
a=[float('-inf')]+list(map(int,input().split()))
if m == 1:
    a.sort()
    print(sum(a[n-k+1:n+1]))
    return
s=[0]*(n+1)
dp=[[0]*(n+1) for _ in range(k+1) ]
for i in range(1,n+1):
    s[i]=s[i-1]+a[i]
for i in range(1,k+1):
    for j in range(i*m,n+1):
        dp[i][j]=max(dp[i][j-1],(s[j]-s[j-m])+dp[i-1][j-m])
print(dp[k][n])

n,m,k=map(int,input().split())
a=[float('-inf')]+list(map(int,input().split()))
if m == 1:
    a.sort()
    print(sum(a[n-k+1:n+1]))
    return
s=[0]*(n+1)
dp=[[0]*(n+1) for _ in range(k+1) ]
for i in range(1,n+1):
    s[i]=s[i-1]+a[i]
for i in range(1,k+1):
    for j in range(i*m,n+1):
        dp[i][j]=max(dp[i][j-1],(s[j]-s[j-m])+dp[i-1][j-m])
print(dp[k][n])

import sys, math
input = sys.stdin.readline

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input().strip()

def listStr():
    return list(input().strip())

import collections as col
import math

def solve():
    N, M, K = getInts()
    P = getInts()
    #suppose we have already chosen i blocks of m, and the last used index was j
    #deal with worst case in order N log N time
    if M == 1:
        P.sort(reverse=True)
        return sum(P[:K])
    PP = [0]
    curr_sum = 0
    for p in P:
        curr_sum += p
        PP.append(curr_sum)
    dp = [[0 for j in range(N+1)] for i in range(K+1)]
    #dp[0][j] = 0 for all j
    #dp[i][0] = 0 for all i
    #Consider dp[1][0] (suppose M==1)
    #dp[1][1] = min(dp[0][1],dp[0][0]+PP[1]-PP[0])
    
    for i in range(1,K+1):
        #j is the number of elements used, i.e. up to index j-1 since it is 0-based
        for j in range(1,N+1):
            if i*M > j:
                continue
            dp[i][j] = max(dp[i][j-1],dp[i-1][j-M]+PP[j]-PP[j-M])
    #print(dp)
    return dp[K][N]
    
print(solve())