#include<bits/stdc++.h> using namespace std; #define int long long const int MX=1e6+100; int n,a[MX],m,k,ans,s[MX]; int minn[MX<<1]; #define lc rt<<1 #define rc rt<<1|1 #define mid (l+r>>1) void build(int rt,int l,int r){ if(l==r){ minn[rt]=s[l];return ; } build(lc,l,mid); build(rc,mid+1,r); minn[rt]=min(minn[lc],minn[rc]); } int query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) return minn[rt]; int ans=1e18; if(L<=mid) ans=min(ans,query(lc,l,mid,L,R)); if(mid+1<=R) ans=min(ans,query(rc,mid+1,r,L,R)); return ans; } signed main(){ ios::sync_with_stdio(0); cin>>n>>m>>k; if(k>=0){ for(int i=1;i<=n;i++) cin>>a[i],a[i]-=k,s[i]=s[i-1]+a[i]; build(1,1,n); for(int i=m;i<=n;i++){ int pos=i-m; int minn=0; if(pos==0){ ans=max(ans,s[i]+m*2*k); continue; } else{ minn=min(minn,query(1,1,n,1,pos)); ans=max(ans,s[i]-minn+m*2*k); } } for(int i=1;i<=n;i++) a[i]+=2*k,s[i]=s[i-1]+a[i]; build(1,1,n); for(int i=1;i<=n;i++){ int pos=0; pos=max(pos,i-m); if(pos==0){ ans=max(ans,s[i]); ans=max(ans,s[i]-query(1,1,n,1,i)); } else{ ans=max(ans,s[i]-query(1,1,n,pos,i)); } } } else{ for(int i=1;i<=n;i++) cin>>a[i],a[i]+=k,s[i]=s[i-1]+a[i]; m=n-m; build(1,1,n); for(int i=m;i<=n;i++){ int pos=i-m; int minn=0; if(pos==0){ ans=max(ans,s[i]-m*2*k); continue; } else{ minn=min(minn,query(1,1,n,1,pos)); ans=max(ans,s[i]-minn-m*2*k); } } for(int i=1;i<=n;i++) a[i]-=2*k,s[i]=s[i-1]+a[i]; build(1,1,n); for(int i=1;i<=n;i++){ int pos=0; pos=max(pos,i-m); if(pos==0){ ans=max(ans,s[i]); ans=max(ans,s[i]-query(1,1,n,1,i)); } else{ ans=max(ans,s[i]-query(1,1,n,pos,i)); } } } cout<<ans; return 0; }