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

Difficulty: interview

Starter code:

Solutions:
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 = 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)

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

# print(part_sum)

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

		# cur_min_in_part_sum_add = part_sum_add[shift][-1] if i == 0 else min(part_sum_add[shift][-1], min_in_part_sum_add[shift][-1])
		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
	# print(shift, part_sum_add[shift], min_in_part_sum_add[shift])

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
	# print('[{}] shift={} min={} ans={}'.format(i, current_shift, current_min, current_ans))
	if current_ans > max_result:
		max_result = current_ans

print(max_result)

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(j, M, ans)
print(ans // m)


import sys
input = sys.stdin.readline
from itertools import accumulate
import copy

n,m,k = list(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 sys
input = sys.stdin.readline
n,m,k=list(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 copy

n,m,k=list(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)
        
    


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)

 #   print("Array:", a, "mid:", mid)
#    print(l_bests)
  #  print(r_bests)
    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)
   # print("Answer:", ans)
    return ans


ans = max_sum(a)
stdout.write(str(ans) + "\n")
#stdout.write(str(bf(a))+"\n")


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)
    #print(best, C)
    bestbest = max(bestbest, best)

print(bestbest)


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




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

__starting_point()

# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import collections
 
#T = int(input())
 
#W,H = [int(x) for x in stdin.readline().split()]
#arr = [int(x) for x in stdin.readline().split()]
 
#s = input()
#N = len(s)
 
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)



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])
        #print(dd)
        #print(dp)
        if (i % m == j):
            mx = max ( mx , dd[i+1]-dp[i+1])
print(mx)

'''input
5 3 10
1 2 10 2 3
'''
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):
		# s = ""
		for j in range(m):
			# s+=str(dp[i][j])+" "
			ma = max(ma,dp[i][j])
		# print(s)
	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)


#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open('input.txt', 'r')
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)]
dp[0][0] = a[0]-k

for i in range(1, n):
	for j in range(m):
		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)

#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open('input.txt', 'r')
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)

n, m, k = list(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 = 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 = 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]
        #if dp[i-1][j] != float()
print(max(max([max(x) for x in dp])-k,0))    

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


n, m, k = list(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)
# print(dp)