You are given an array $a_1, a_2, \dots , a_n$ and two integers $m$ and $k$.

You can choose some subarray $a_l, a_{l+1}, \dots, a_{r-1}, a_r$. 

The cost of subarray $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ is equal to $\sum\limits_{i=l}^{r} a_i - k \lceil \frac{r - l + 1}{m} \rceil$, where $\lceil x \rceil$ is the least integer greater than or equal to $x$. 

The cost of empty subarray is equal to zero.

For example, if $m = 3$, $k = 10$ and $a = [2, -4, 15, -3, 4, 8, 3]$, then the cost of some subarrays are:  $a_3 \dots a_3: 15 - k \lceil \frac{1}{3} \rceil = 15 - 10 = 5$;  $a_3 \dots a_4: (15 - 3) - k \lceil \frac{2}{3} \rceil = 12 - 10 = 2$;  $a_3 \dots a_5: (15 - 3 + 4) - k \lceil \frac{3}{3} \rceil = 16 - 10 = 6$;  $a_3 \dots a_6: (15 - 3 + 4 + 8) - k \lceil \frac{4}{3} \rceil = 24 - 20 = 4$;  $a_3 \dots a_7: (15 - 3 + 4 + 8 + 3) - k \lceil \frac{5}{3} \rceil = 27 - 20 = 7$. 

Your task is to find the maximum cost of some subarray (possibly empty) of array $a$.


-----Input-----

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 3 \cdot 10^5, 1 \le m \le 10, 1 \le k \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$).


-----Output-----

Print the maximum cost of some subarray of array $a$.


-----Examples-----
Input
7 3 10
2 -4 15 -3 4 8 3

Output
7

Input
5 2 1000
-13 -4 -9 -20 -11

Output
0

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Mathematics

Greedy algorithms


Solutions:
import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
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))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = [[0 for i in range(m)] for j in range(n)]
	ans = 0
	for i in range(n):
		if m == 1:
			if i:
				dp[i][0] = max(a[i] - k, dp[i - 1][0] + a[i] - k)
			else:
				dp[i][0] = a[i] - k
			ans = max(ans, dp[i][0])
		elif i:
			for j in range(m):
				if j <= i + 1 and j >= 1 or (j == 0 and i >= m - 1):
					if j != 1:
						dp[i][j] = dp[i - 1][(j - 1 + m) % m] + a[i]
					else:
						dp[i][1] = max(a[i] - k, dp[i - 1][0] + a[i] - k)
					ans = max(ans, dp[i][j])
		else:
			dp[i][1] = a[i] - k
			ans = max(ans, a[i] - k)
	print(ans)
	return
main()


import sys, math, queue
MOD = 998244353
sys.setrecursionlimit(1000000)
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
dp = [[-10 ** 20 for i in range(m)] for i in range(n)]
for i in range(n):
	for j in range(min(m, i + 1)):
		if j == 0:
			dp[i][j] = max(dp[i - 1][m - 1] + a[i], a[i]) - k
		else:
			dp[i][j] = dp[i - 1][j - 1] + a[i]
ans = 0
for i in range(n):
	ans = max(ans, max(dp[i]))
print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	(N, M, K) = map(int, input().split())
	A = list(map(int, input().split()))
	cs = [0] * (N + 1)
	mi = [10 ** 10] * M
	mi[0] = 0
	ans = 0
	for (i, a) in enumerate(A):
		cs[i + 1] = cs[i] + (a - K / M)
		mi[(i + 1) % M] = min(mi[(i + 1) % M], cs[i + 1])
		for j in range(M):
			ans = max(ans, cs[i + 1] - mi[(i + 1 + j) % M] - K / M * j)
	print(max(int(ans + 0.5), 0))
main()


def naiveSolve(n, m, k, a):
	ans = 0
	(L, R) = (-1, -1)
	for l in range(n):
		t = 0
		for r in range(l, n):
			t += a[r]
			temp = t - k * ((r - l + 1 + m - 1) // m)
			if temp > ans:
				ans = temp
				(L, R) = (l, r)
	return (ans, L, R)
	return

def main():
	(n, m, k) = readIntArr()
	a = readIntArr()
	p = a.copy()
	for i in range(1, n):
		p[i] += p[i - 1]

	def rangeSum(l, r):
		if l == 0:
			return p[r]
		else:
			return p[r] - p[l - 1]
	dp = [0] * n
	for i in range(n):
		if i - m >= 0:
			dp[i] = max(dp[i], dp[i - m] + rangeSum(i - m + 1, i) - k)
		for j in range(max(0, i - m + 1), i + 1):
			dp[i] = max(dp[i], rangeSum(j, i) - k)
	ans = max(dp)
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


(n, m, k) = map(int, input().split())
z = list(map(int, input().split()))
import math
ans = [[0, 0, 0] for i in range(len(z))]
for i in range(len(z)):
	if i + 1 <= m:
		for j in range(m):
			total = sum(z[i - j:i + 1])
			if total - k > ans[i][0]:
				ans[i][0] = total - k
				ans[i][1] = j + 1
				ans[i][2] = total
	else:
		for j in range(m + 1):
			if j == 0:
				ans[i][0] = max(z[i] - k, ans[i][0])
				if z[i] - k == ans[i][0]:
					ans[i][1] = 1
					ans[i][2] = z[i]
			else:
				score = ans[i - j][2] + sum(z[i - j + 1:i + 1]) - k * math.ceil((ans[i - j][1] + j) / m)
				if score > ans[i][0]:
					ans[i][0] = score
					ans[i][1] = ans[i - j][1] + j
					ans[i][2] = ans[i - j][2] + sum(z[i - j + 1:i + 1])
maxa = 0
for i in range(len(z)):
	maxa = max(maxa, ans[i][0])
print(maxa)


(n, m, k) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
a = [0] + a
dp = [0] * 300005
ans = 0
for i in range(1, n + 1):
	a[i] += a[i - 1]
	for j in range(1, m + 1):
		if i - j >= 0:
			dp[i] = max(dp[i], a[i] - a[i - j] - k)
	if i - m >= 0:
		dp[i] = max(dp[i], a[i] - a[i - m] + dp[i - m] - k)
	ans = max(ans, dp[i])
print(ans)


import sys
(n, m, k) = list(map(int, sys.stdin.readline().strip().split()))
a = list(map(int, sys.stdin.readline().strip().split()))
b = [0] * (n + 1)
for i in range(1, n + 1):
	b[i] = b[i - 1] + m * a[i - 1] - k
M = [10 ** 20] * m
ans = 0
for i in range(0, n + 1):
	M[i % m] = min([M[i % m], b[i]])
	for j in range(0, m):
		if i > j:
			ans = max([ans, b[i] - M[j] - k * ((m * i + m - (i - j)) % m)])
print(ans // m)


from sys import stdin, stdout, exit
(n, m, k) = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().split()))

def bf(a):
	best = 0
	best_arg = (-1, -1)
	for i in range(n):
		for j in range(i, n):
			cur = sum(a[i:j + 1]) - k * ((j - i) // m + 1)
			if cur > best:
				best = max(best, cur)
				best_arg = (i, j)
	return (best, best_arg)

def max_sum(a):
	if len(a) == 0:
		return 0
	elif len(a) == 1:
		return max(0, a[0] - k)
	mid = len(a) // 2
	l_rec = max_sum(a[:mid])
	r_rec = max_sum(a[mid:])
	l_bests = [0] * m
	r_bests = [0] * m
	l_sum = 0
	for idx in range(1, mid + 1):
		l_sum += a[mid - idx]
		if idx % m == 0:
			l_sum -= k
		l_bests[idx % m] = max(l_bests[idx % m], l_sum)
	r_sum = 0
	for idx in range(0, len(a) - mid):
		r_sum += a[idx + mid]
		if (idx + 1) % m == 0:
			r_sum -= k
		r_bests[(idx + 1) % m] = max(r_bests[(idx + 1) % m], r_sum)
	best_acr = 0
	for i in range(m):
		for j in range(m):
			best_acr = max(best_acr, l_bests[i] + r_bests[j] - (k if i + j > 0 else 0) - (k if i + j > m else 0))
	ans = max(l_rec, r_rec, best_acr)
	return ans
ans = max_sum(a)
stdout.write(str(ans) + '\n')


base = 1000000007
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
mx = 0
s = 0
dp = []
dd = []
for j in range(m):
	for i in range(n + 1):
		dp.append(base)
		dd.append(0)
	for i in range(n):
		dd[i + 1] = dd[i] + a[i] - k * (i % m == j)
		dp[i + 1] = min(dd[i], dp[i])
		if i % m == j:
			mx = max(mx, dd[i + 1] - dp[i + 1])
print(mx)


(N, M, K) = list(map(int, input().split()))
A = [int(a) for a in input().split()]
S = [0]
for a in A:
	S.append(S[-1] + M * a - K)
MI = [10 ** 50] * M
ans = 0
for i in range(N + 1):
	MI[i % M] = min(MI[i % M], S[i])
	for j in range(M):
		ans = max(ans, (S[i] - MI[(i - j) % M] - K * (-j % M)) // M)
print(ans)


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


import sys
input = sys.stdin.readline
from itertools import accumulate
import copy
(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
ANS = 0
for i in range(m):
	B = copy.deepcopy(A)
	for j in range(i, n, m):
		B[j] -= k
	SUM = list(accumulate(B))
	SUMMIN = [float('inf')] * n + [0]
	if i == 0:
		SUMMIN[0] = 0
	for j in range(max(1, i), n):
		if j % m == i % m:
			SUMMIN[j] = min(SUMMIN[j - 1], SUM[j - 1])
		else:
			SUMMIN[j] = SUMMIN[j - 1]
	for j in range(i, n):
		ANS = max(ANS, SUM[j] - SUMMIN[j])
print(ANS)


import math

def max_sub(arr, n):
	dp = [0] * n
	dp[0] = arr[0]
	for i in range(1, n):
		dp[i] = max(dp[i - 1] + arr[i], arr[i])
	return max(0, max(dp))
(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
q = -math.inf
dp = [0] * 300100
for i in range(300100):
	dp[i] = [q] * 11
if m == 1:
	for i in range(n):
		arr[i] = arr[i] - k
	print(max_sub(arr, n))
else:
	for i in range(n):
		dp[i][1] = arr[i] - k
		for j in range(m):
			if i - 1 < 0 or dp[i - 1][j] == q:
				continue
			if (j + 1) % m != 1:
				dp[i][(j + 1) % m] = dp[i - 1][j] + arr[i]
			else:
				dp[i][(j + 1) % m] = max(arr[i] - k, dp[i - 1][j] + arr[i] - k)
	ma = 0
	for i in range(n):
		for j in range(m):
			ma = max(ma, dp[i][j])
	print(ma)


(N, M, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
bv = 0
for ms in range(M):
	cv = 0
	for i in range(ms, N):
		v = A[i]
		if i % M == ms:
			v -= K
			cv = max(0, cv)
		cv += v
		bv = max(bv, cv)
print(bv)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
sa = [0] * n
ans = 0
for i in range(n):
	sa[i] = a[i] - k
	s = a[i]
	for j in range(i - 1, max(-1, i - m - 1), -1):
		sa[i] = max(sa[i], sa[j] + s - k)
		s += a[j]
	if i < m:
		sa[i] = max(sa[i], s - k)
	sa[i] = max(sa[i], 0)
	ans = max(ans, sa[i])
print(ans)


(n, m, k) = [int(w) for w in input().split()]
a = [int(w) for w in input().split()]

def f(o):
	r = e = 0
	for (i, x) in enumerate(a):
		if i < o:
			continue
		if i % m == o:
			e -= k
			if e < -k:
				e = -k
		e += x
		if e > r:
			r = e
	return r
print(max((f(o) for o in range(m))))


import sys
import math as mt
import bisect
input = sys.stdin.readline
t = 1

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def solve():
	pre = 0
	dp = [0] * (n + 1)
	ans = 0
	for i in range(n):
		(ss, maxi) = (0, 0)
		if i < m:
			pre += l[i]
		else:
			pre += l[i]
			pre -= l[i - m]
		for j in range(i, max(i - m, -1), -1):
			ss += l[j]
			maxi = max(maxi, ss - k)
		if i >= m:
			dp[i] = max(dp[i - m] + pre - k, maxi)
		else:
			dp[i] = max(dp[i], maxi)
		ans = max(dp[i], ans)
	return ans
for _ in range(t):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	pref = [0] * (n + 1)
	for i in range(n):
		pref[i + 1] = pref[i] + l[i]
	print(solve())


import copy
(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
ANS = 0
for i in range(m):
	B = copy.deepcopy(A)
	for j in range(i, n, m):
		B[j] -= k
	NOW = 0
	for j in range(i, n):
		if j % m == i:
			NOW = max(NOW + B[j], B[j])
		else:
			NOW += B[j]
		ANS = max(ANS, NOW)
print(ANS)


def maxsum(a):
	best = 0
	cur = 0
	for e in a:
		cur = max(cur, 0) + e
		best = max(best, cur)
	return best

def solve(m, k, a):
	if m == 1:
		return maxsum([e - k for e in a])
	best = 0
	cur = [-k] * m
	for e in a:
		new_cur = [max(0, cur[0]) + e - k if i == 1 else cur[(i - 1) % m] + e for i in range(m)]
		best = max(best, max(new_cur))
		cur = new_cur
	return best
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
print(solve(m, k, a))


(n, m, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [float('inf') for i in range(m)]
count = 0
dp[0] = k
maxi = 0
for i in range(1, n + 1):
	count += a[i]
	maxi = max(maxi, count - min(dp))
	dp[i % m] = min(dp[i % m], count)
	dp[i % m] += k
print(maxi)


import itertools
(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
acc = [0] + list(itertools.accumulate(A))
rsum = lambda i, j: acc[j + 1] - acc[i]
dp = [0] * n
ans = 0
for (i, a) in enumerate(A):
	if i >= m:
		dp[i] = max(dp[i], dp[i - m] + rsum(i - m + 1, i) - k)
	for j in range(i, max(-1, i - m), -1):
		dp[i] = max(dp[i], rsum(j, i) - k)
	ans = max(ans, dp[i])
print(ans)


def max_subarray(A):
	max_ending_here = max_so_far = A[0]
	for x in A[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far
ans = 0
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
	li = a[0:i] + [-k]
	s = 0
	while True:
		li += a[i + s:min(i + m + s, len(a))]
		li += [-k]
		if i + m + s >= len(a):
			break
		s += m
	ans = max(max_subarray(li) - k, ans)
print(ans)


import sys
import math
from collections import defaultdict, deque
import heapq
mod = 998244353
(n, m, k) = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
dp = [[0 for _ in range(m)] for x in range(n)]
ans = 0
for i in range(n):
	x = 0
	if i - m >= 0:
		x = max(x, dp[i - m][m - 1])
	s = 0
	for j in range(i, min(n, i + m)):
		s += arr[j]
		dp[i][j - i] = s - k + x
		ans = max(ans, dp[i][j - i])
print(ans)


(n, m, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
values = list()
for j in range(n):
	result = a[j]
	sum1 = 0
	for i in range(m):
		if j - i >= 0:
			sum1 = sum1 + a[j - i]
			if sum1 > result:
				result = sum1
		else:
			continue
	if j - m >= 0:
		result = max(result, sum1 + values[j - m])
	values.append(max(0, result - k))
print(max(values))


(n, m, k) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
bestbest = 0

def brute(n, m, k, A):
	ans = 0
	val = (0, 0)
	for i in range(n):
		for j in range(i, n):
			if ans < sum(A[i:j + 1]) - k * ceil((j - i + 1) / m):
				ans = sum(A[i:j + 1]) - k * ceil((j - i + 1) / m)
				val = (i, j)
	return (val, ans)
for off in range(m):
	B = A[off:]
	C = []
	canstart = []
	for i in range(len(B)):
		if i % m == 0:
			C.append(-k)
			canstart.append(1)
		canstart.append(0)
		C.append(B[i])
	best = 0
	run = 0
	for i in range(len(C)):
		run += C[i]
		if run < -k:
			run = -k
		best = max(best, run)
	bestbest = max(bestbest, best)
print(bestbest)


from itertools import accumulate
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
als = []
for i in range(m):
	ls = a[:]
	for j in range(n):
		if j % m == i:
			ls[j] -= k
	als.append(list(accumulate(ls)))
ans = 0
for i in range(m):
	ls = als[i]
	mn = 0
	anstmp = 0
	for j in range(n):
		if mn > ls[j]:
			mn = ls[j]
		if j % m == i:
			anstmp = max(anstmp, ls[j] - mn)
	ans = max(ans, anstmp)
print(ans)


(n, m, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
ret = 0
for i in range(m):
	cur = 0
	for j in range(i, n):
		if j % m == i:
			cur = max(0, cur)
			cur -= k
		cur += a[j]
		ret = max(ret, cur)
print(ret)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
best = 0
dp = [0] * (n + 1)
for i in range(n):
	b2 = 0
	for j in range(max(-1, i - m), i + 1):
		b2 = max(b2, dp[j] - k + sum(a[j + 1:i + 1]))
	dp[i] = max(b2, a[i] - k)
	best = max(best, dp[i])
print(best)


(n, m, k) = map(int, input().split())
b = [0] + list(map(int, input().split()))
rem = [float('inf') for i in range(m)]
rem[0] = k
curr = 0
ans = 0
for i in range(1, n + 1):
	curr += b[i]
	ans = max(ans, curr - min(rem))
	rem[i % m] = min(rem[i % m], curr)
	rem[i % m] += k
print(ans)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
from collections import defaultdict, deque
import heapq
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = pow(10, 9) + 7
BUFSIZE = 8192
import bisect

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

def sieve_of_eratosthenes(n):
	all_prime = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			all_prime.append(p)
	return all_prime
s = sieve_of_eratosthenes(int(math.sqrt(10 ** 9)) + 1)
ls = len(s)
(n, m, k) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
ans = 0
for i in range(m):
	c = 0
	for j in range(i, n):
		if j % m == i:
			c = max(0, c)
			c -= k
		c += l[j]
		ans = max(ans, c)
print(ans)


import os
import sys
from io import BytesIO, IOBase
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')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, m, k) = RL()
	arr = RLL()
	res = 0
	for i in range(m):
		narr = [j for j in arr]
		for j in range(i, n, m):
			narr[j] -= k
		sm = 0
		mi = 0
		for j in range(n):
			sm += narr[j]
			mi = min(mi, sm)
			if j % m == i:
				res = max(res, sm - mi)
	print(res)
main()


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
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')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def maxSubArraySum(a, size):
	max_so_far = 0
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
if m == 1:
	l = [l[i] - k for i in range(n)]
	print(max(0, maxSubArraySum(l, n)))
	sys.exit(0)
dp = [[0 for i in range(m)] for j in range(n)]
dp[0][1] = l[0] - k
for i in range(1, n):
	for j in range(min(i + 2, m)):
		if j == 0:
			dp[i][0] = max(0, dp[i - 1][m - 1] + l[i])
			if i < m - 1:
				dp[i][0] = 0
		elif j == 1:
			dp[i][j] = max(l[i], dp[i - 1][0] + l[i]) - k
		else:
			dp[i][j] = dp[i - 1][j - 1] + l[i]
ans = 0
for i in range(n):
	for j in range(m):
		ans = max(ans, dp[i][j])
print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	inf = 10 ** 18
	dp = [0] + [inf] * (m - 1)
	add = [k] + [0] * (m - 1)
	(acc, ans) = (0, 0)
	for (i, x) in enumerate(a, start=1):
		acc += x
		ans = max(ans, acc - min((dp[j] + add[j] for j in range(m))))
		dp[i % m] = min(dp[i % m], acc - add[i % m])
		add[i % m] += k
	print(ans)
main()


from math import *
(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
a = [0 for i in range(n + 1)]
ans = 0
for M in range(m):
	min1 = 0
	for i in range(1, n + 1):
		a[i] = a[i - 1] + l[i - 1]
		if i % m == M:
			a[i] -= k
			ans = max(ans, a[i] - min1)
		min1 = min(min1, a[i])
print(ans)


(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
glans = 0
for s in range(m):
	B = []
	f = s
	su = 0
	sus = 0
	for i in range(s, n):
		su += A[i]
		sus = max(sus, su)
		if (i + 1) % m == s:
			B.append(sus - k)
			B.append(su - sus)
			su = 0
			sus = 0
			f = i + 1
	dob = 0
	klol = 0
	for j in range(f, n):
		dob += A[j]
		klol = max(klol, dob - k)
	B = [0] + B + [klol]
	for i in range(1, len(B)):
		B[i] += B[i - 1]
	cnt = -10 ** 10
	ans = [0, 0]
	minsum = 10 ** 10
	candidat = 0
	for i in range(len(B)):
		if B[i] - minsum > cnt:
			cnt = B[i] - minsum
			ans[1] = i
			ans[0] = candidat
		if B[i] <= minsum:
			minsum = B[i]
			candidat = i
	glans = max(glans, B[ans[1]] - B[ans[0]])
print(glans)


import math
(n, m, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
part_sum = [0]
for i in range(n):
	part_sum.append(part_sum[-1] + arr[i])
part_sum_add = [[] for _ in range(m)]
min_in_part_sum_add = [[] for _ in range(m)]
for shift in range(m):
	count_blocks = math.ceil((n - shift) / m + 1)
	for i in range(n + 1):
		cur_part_sum = part_sum[i] + k * (count_blocks - (i - shift) // m)
		if i == 0 or cur_part_sum < prev_min_in_part_sum_add:
			cur_min_in_part_sum_add = cur_part_sum
		else:
			cur_min_in_part_sum_add = prev_min_in_part_sum_add
		part_sum_add[shift].append(cur_part_sum)
		min_in_part_sum_add[shift].append(cur_min_in_part_sum_add)
		prev_min_in_part_sum_add = cur_min_in_part_sum_add
max_result = 0
for i in range(1, n + 1):
	current_shift = i % m
	current_min = min_in_part_sum_add[current_shift][i]
	current_ans = part_sum_add[current_shift][i] - current_min
	if current_ans > max_result:
		max_result = current_ans
print(max_result)


import sys

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]

def main():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for mod in range(m):
		b = [0] + a.copy()
		for i in range(1, n + 1):
			if i % m == mod:
				b[i] += -k
		for i in range(1, n + 1):
			b[i] += b[i - 1]
		for i in reversed(range(1, n + 1)):
			if i + 1 <= n:
				b[i] = max(b[i], b[i + 1])
			if i % m != mod:
				continue
			ans = max(ans, b[i] - b[i - 1])
	print(ans)
	return 0
main()


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
A = [int(i) for i in input().split()]
if n <= m:
	AA = [0] * (n + 1)
	for i in range(n):
		AA[i + 1] = AA[i] + A[i]
	mm = 0
	for i in range(n + 1):
		for j in range(i + 1, n + 1):
			mm = max(mm, AA[j] - AA[i] - k)
else:
	DP = [[0] * (m + 1) for _ in range(n + 1)]
	for i in range(n):
		a = A[i]
		DP[i + 1][0] = max([DP[i][0], DP[i][m], DP[i][m] + a - k, DP[i][1]])
		DP[i + 1][1] = max(a - k, DP[i][m] + a - k)
		for j in range(2, m + 1):
			DP[i + 1][0] = max(DP[i + 1][0], DP[i][j])
			if j > i + 1:
				continue
			else:
				DP[i + 1][j] = max(DP[i][j - 1] + a, DP[i][m] + a - k)
print(max(A[0] - k, 0) if n == 1 else mm if n <= m else max(0, max(DP[n])))


import io, sys
input = lambda f=io.StringIO(sys.stdin.buffer.read().decode()).readline: f().rstrip()
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(n, m, k) = mi()
a = [None] + li()
p = [0] * (n + 1)
for i in range(1, n + 1):
	p[i] = p[i - 1] + a[i]
s = [10 ** 16 for _ in range(m)]
s[0] = k
ans = 0
for i in range(1, n + 1):
	ans = max(ans, p[i] - min(s))
	s[i % m] = min(s[i % m], p[i])
	s[i % m] += k
print(ans)


import sys

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def string(s):
	return ''.join(s)

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def bo(i):
	return ord(i) - ord('A')

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j):
	return 0 <= i < n and 0 <= j < m and (a[i][j] != '.')

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
while t > 0:
	t -= 1
	(n, m, k) = mi()
	a = li()
	d = [[] for i in range(m + 1)]
	pre = [a[0]]
	for i in range(1, n):
		pre.append(pre[-1] + a[i])
	pre.append(0)
	l = [[] for i in range(m + 1)]
	for i in range(m):
		maxi = -10 ** 18
		for j in range(i, n):
			if j > i and (j - i) % m == 0:
				d[i].append(maxi - (j - i) // m * k)
				l[i].append(maxi)
				maxi = -10 ** 18
			maxi = max(maxi, pre[j])
		if maxi != -10 ** 18:
			d[i].append(maxi - ((j - i) // m + 1) * k)
			l[i].append(maxi)
	for i in range(m):
		for j in range(len(d[i]) - 2, -1, -1):
			d[i][j] = max(d[i][j + 1], d[i][j])
	maxi = 0
	for i in range(n):
		c = d[i % m][i // m] + i // m * k - pre[i - 1]
		maxi = max(maxi, c)
	print(maxi)


(n, m, k) = map(int, input().split())
(*a,) = map(int, input().split())
dp = [-1] * (n + 15)
for i in range(n):
	(s, mx) = (a[i], max(0, a[i]))
	for j in range(i - 1, max(-1, i - m), -1):
		s += a[j]
		mx = max(mx, s)
	dp[i] = max(0, dp[i - m] + s - k, mx - k)
print(max(dp))


(n, m, k) = map(int, input().split())
aa = list(map(int, input().split()))
ans = 0
for start in range(m):
	ac = aa[:]
	for i in range(start, n, m):
		ac[i] -= k
	cur = 0
	for i in range(start, n):
		if i % m == start:
			cur = max(ac[i] + cur, ac[i])
		else:
			cur += ac[i]
		ans = max(cur, ans)
print(ans)


def getBestWindow(N, M, K, a):
	(dp, ans) = ([], 0)
	for i in range(0, N):
		dp.append(a[i] - K)
		(sum, x) = (a[i], max(0, i - M))
		for j in range(i - 1, x - 1, -1):
			dp[i] = max(dp[i], dp[j] + sum - K)
			sum += a[j]
		if i < M:
			dp[i] = max(dp[i], sum - K)
		dp[i] = max(dp[i], 0)
		ans = max(ans, dp[i])
	return ans
(N, M, K) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
ans = getBestWindow(N, M, K, arr)
print(ans)


from sys import stdin, stdout
import collections
(N, M, K) = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
res = 0
for j in range(M):
	s = 0
	mini = 0
	for i in range(j, N):
		if i % M == j:
			mini = min(mini, s)
			s -= K
		s += arr[i]
		res = max(res, s - mini)
print(res)