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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Implementation


Solutions:
from sys import stdin
input = stdin.readline

def put():
	return map(int, input().split())
(n, m, k) = put()
l = list(put())
if m == 1:
	l.sort(reverse=True)
	print(sum(l[:k]))
	exit()
p = []
summ = 0
for i in range(m):
	summ += l[i]
p.append(summ)
for i in range(m, n):
	summ += l[i] - l[i - m]
	p.append(summ)
r = p.copy()
c = len(p)
q = [0] * c
for j in range(k):
	for i in range(j, c):
		q[i] = p[i]
		if i - m >= 0 and j > 0:
			q[i] += r[i - m]
		if i - 1 >= 0:
			q[i] = max(q[i - 1], q[i])
	r = q.copy()
print(r[-1])


(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])


(n, m, k) = map(int, input().split())
p = list(map(int, input().split()))
if m == 1:
	print(sum(sorted(p)[-k:]))
	exit()
s = sum(p[:m])
(i, j) = (0, m)
l = [s]
while j < n:
	s = s - p[i] + p[j]
	i += 1
	j += 1
	l.append(s)
n = len(l)
dp = [[0] * (n + 1) for i in range(k + 1)]
for i in range(1, n + 1):
	dp[1][i] = max(dp[1][i - 1], l[i - 1])
for i in range(2, k + 1):
	for j in range(m * (i - 1) + 1, n + 1):
		dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - m] + l[j - 1])
print(dp[-1][-1])


(n, m, k) = map(int, input().split())
p = list(map(int, input().split()))
ac = [p[i] for i in range(n)]
for i in range(1, n):
	ac[i] += ac[i - 1]
dp = [0] * n
for kk in range(1, k + 1):
	ndp = [0] * n
	for i in range(kk * m - 1, n - (k - kk) * m):
		ndp[i] = max(dp[i - m] + ac[i] - (ac[i - m] if i - m >= 0 else 0), ndp[i - 1])
	dp = ndp
print(max(dp))


(n, m, k) = map(int, input().split(' '))
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])


import math

def func(i, k):
	global prefix
	global m
	global dp
	for i in range(n):
		for j in range(k + 1):
			if j == 0 or i < m - 1:
				dp[i][j] = 0
			elif i == m - 1:
				if j == 1:
					dp[i][j] = prefix[i]
				else:
					dp[i][j] = -math.inf
			else:
				dp[i][j] = max(dp[i - 1][j], prefix[i] - prefix[i - m] + dp[i - m][j - 1])
	return dp[n - 1][k]
(n, m, k) = tuple(map(int, input().split()))
a = list(map(int, input().split()))
prefix = [0] * n
for i in range(n):
	if i == 0:
		prefix[i] = a[i]
	else:
		prefix[i] = prefix[i - 1] + a[i]
dp = [[-1 for i in range(k + 1)] for j in range(n)]
if m * k == n:
	print(sum(a))
else:
	print(func(n - 1, k))


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()
	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)]
	for i in range(1, K + 1):
		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])
	return dp[K][N]
print(solve())


(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[k][n])


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])


(n, m, k) = 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)
	exit()
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 = [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])


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)
	exit()
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])
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)


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)
(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()


(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(1, n):
	arr[i] += arr[i - 1]
for i in range(n - 1, m - 1, -1):
	arr[i] -= arr[i - m]
dp = [0] * n
for ink in range(1, k + 1):
	ndp = [0] * n
	for i in range(ink * m - 1, n - (k - ink) * m):
		ndp[i] = max(dp[i - m] + arr[i], ndp[i - 1])
	dp = ndp[:]
print(dp[n - 1])


dicti = {}
INF = -float('inf')

def dp(ind, k):
	if k == 0:
		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)]
	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])


import sys

def solve(n, m, k, 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] = 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]
(n, m, k) = map(int, sys.stdin.readline().strip().split())
numbers = list(map(int, sys.stdin.readline().strip().split()))
r = solve(n, m, k, numbers)
print(r)


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m, k) = gil()
a = gil()
if m == 1:
	a.sort()
	print(sum(a[-k:]))
else:
	prefix = a[:]
	for i in range(1, n):
		prefix[i] += prefix[i - 1]

	def getSum(l, r):
		return prefix[r] - (prefix[l - 1] if l and r - l + 1 == m else 0)
	dp = [[0 for _ in range(n)] for _ in range(k + 1)]
	for k in range(1, k + 1):
		for i in range(n):
			v1 = dp[k - 1][i - m] if i >= m else 0
			dp[k][i] = max(v1 + getSum(max(0, i + 1 - m), i), dp[k][i - 1] if i else 0)
	print(dp[-1][-1])


def job(arr, m, k):
	if k == len(arr) and m == 1:
		return sum(arr)
	pf = [0]
	cnst = 0
	for i in arr:
		cnst += i
		pf.append(cnst)
	dp = [[0] * len(pf) for i in range(k + 1)]
	for i in range(k):
		for j in range(len(pf)):
			if i * m > j:
				dp[i][j] = 0
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - m] + pf[j] - pf[j - m])
	return dp[k - 1][-1]
(a, b, c) = map(int, input().strip().split())
lst = list(map(int, input().strip().split()))
print(job(lst, b, c))


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:]))
	exit(0)
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])


def main():
	(n, m, k) = 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])
main()


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	try:
		(n, m, k) = invr()
		a = inlt()
		if m == 1:
			print(sum(sorted(a, reverse=True)[:k]))
			return True
		(pre, x) = ([0], 0)
		for i in range(n):
			x += a[i]
			pre.append(x)
		dp = [[0] * (n + 1) for i in range(k + 1)]
		for i in range(1, k + 1):
			for j in range(i * m, n + 1):
				dp[i][j] = max(dp[i][j - 1], pre[j] - pre[j - m] + dp[i - 1][j - m])
		print(dp[k][n])
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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())
p = list(map(int, input().split()))
lst = [0]
s = 0
for i in range(n):
	s += p[i]
	lst.append(s)
if n - k * m == 0:
	print(lst[-1])
elif m == 1:
	new = sorted(p)
	ans = 0
	for i in range(len(new) - 1, len(new) - k - 1, -1):
		ans += new[i]
	print(ans)
else:
	dp = [[0 for j in range(n + 1)] for i in range(k + 1)]
	for i in range(1, k + 1):
		for j in range(m, n + 1):
			price = lst[j] - lst[j - m]
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - m] + price)
	print(dp[k][n])


(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])


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		(n, m, k) = LI()
		a = LI()
		if m == 1:
			rr.append(sum(sorted(a)[-k:]))
			continue
		dp = [[0] * (n + 1) for _ in range(k + 1)]
		t = sum(a[:m])
		dp[1][m - 1] = t
		for i in range(m, n):
			t -= a[i - m]
			t += a[i]
			x = 0
			for j in range(k):
				dp[j + 1][i] = max(dp[j + 1][i - 1], dp[j][i - m] + t)
		rr.append(max(dp[-1]))
	return JA(rr, '\n')
print(main())


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
if m == 1:
	print(sum(sorted(a)[n - k:n]))
else:
	s = list((sum(a[i:i + m]) for i in range(0, n - m + 1)))
	dp = [[-1 for i in range(k + 1)] for j 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])


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]))
	exit()
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])


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


(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) = list(map(int, input().split()))
a = list(map(int, input().split()))
p_a = [0 for _ in range(n)]
p_a[0] = a[0]
for i in range(1, n):
	p_a[i] = p_a[i - 1] + a[i]
INF = -10000000000.0
dp = {}
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def solve(i, k, m):
	if (i, k, m) in dp:
		yield dp[i, k, m]
	if k == 0:
		dp[i, k, m] = 0
		yield 0
	if i + m == n:
		if k == 1:
			if i == 0:
				dp[i, k, m] = p_a[n - 1]
			else:
				dp[i, k, m] = p_a[n - 1] - p_a[i - 1]
			yield dp[i, k, m]
		if k > 1:
			dp[i, k, m] = INF
			yield INF
	if i + m > n - 1:
		dp[i, k, m] = INF
		yield INF
	if k == 0:
		dp[i, k, m] = 0
		yield 0
	if i == 0:
		a = (yield solve(i + 1, k, m))
		b = (yield solve(i + m, k - 1, m))
		dp[i, k, m] = max(a, b + p_a[i + m - 1])
		yield dp[i, k, m]
	else:
		a = (yield solve(i + 1, k, m))
		b = (yield solve(i + m, k - 1, m))
		dp[i, k, m] = max(a, b + p_a[i + m - 1] - p_a[i - 1])
		yield dp[i, k, m]
if m == 1:
	print(sum(sorted(a)[n - k:]))
else:
	print(solve(0, k, m))