#include<bits/stdc++.h> #define int long long using namespace std; const int MAXN=2e5+10; int n,k,x,cnt,ans; int b[MAXN],lx,rx,tmp,an; int a[MAXN]; int s[MAXN],S[MAXN]; int c[4*MAXN],d[4*MAXN]; void build1(int l,int r,int x) { if(l==r) { c[x]=s[l]; return; } int mid=l+r>>1; build1(l,mid,x*2); build1(mid+1,r,x*2+1); c[x]=max(c[x*2],c[x*2+1]); } int res1(int l,int r,int dl,int dr,int x) { // cout<<l<<r<<c[x]<<endl; if(dl<=l&&r<=dr) return c[x]; int mid=l+r>>1; int tmp=-LLONG_MAX; if(dl<=mid) tmp=max(res1(l,mid,dl,dr,x*2),tmp); if(mid+1<=dr) tmp=max(res1(mid+1,r,dl,dr,x*2+1),tmp); return tmp; } void build2(int l,int r,int x) { if(l==r) { d[x]=S[l]; return; } int mid=l+r>>1; build2(l,mid,x*2); build2(mid+1,r,x*2+1); d[x]=max(d[x*2],d[x*2+1]); } int res2(int l,int r,int dl,int dr,int x) { if(dl<=l&&r<=dr) return d[x]; int mid=l+r>>1; int tmp=-LLONG_MAX; if(dl<=mid) tmp=max(res2(l,mid,dl,dr,x*2),tmp); if(mid<dr) tmp=max(res2(mid+1,r,dl,dr,x*2+1),tmp); return tmp; } signed main() { cin>>n>>k>>x; if(x<0) k=n-k,x=-x; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; for(int i=n;i>=1;i--) S[i]=S[i+1]+a[i]; if(k==0) { int mx=-LLONG_MAX,mi=LLONG_MAX,kx=n,ki=0; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-x; for(int i=n;i>=1;i--) S[i]=S[i+1]+a[i]-x; for(int i=0;i<=n;i++) { if(s[i]>mx) mx=s[i],kx=i; if(s[i]<mi) mi=s[i],ki=i; } if(mx-mi>0&&kx>ki) cout<<mx-mi<<endl; else cout<<0<<endl; return 0; } for(int i=1;i<=n;i++) { if(s[i+k-1]-s[i-1]==ans) { b[++cnt]=i; } if(s[i+k-1]-s[i-1]>ans) { cnt=0; ans=s[i+k-1]-s[i-1]; b[++cnt]=i; } } ans+=k*x; //cout<<ans<<endl; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-x; for(int i=n;i>=1;i--) S[i]=S[i+1]+a[i]-x; if(n<=5e3+10) { for(int i=1;i<=cnt;i++) { tmp=0; int l=b[i],r=b[i]+k-1; int ll=l,rr=r; lx=rx=0; for(int j=l;j>=1;j--) { lx=max(lx,S[j]-S[l]); } tmp+=lx; for(int j=r;j<=n;j++) { rx=max(rx,s[j]-s[r]); } tmp+=rx; // cout<<lx<<" "<<rx<<endl; an=max(an,tmp); } cout<<ans+an<<endl; return 0; } else { build1(1,n,1); build2(1,n,1); for(int i=1;i<=cnt;i++) { tmp=0; int l=b[i],r=b[i]+k-1; lx=rx=0; if(l!=1) lx=max(res2(1,n,1,l-1,1)-S[l],lx); if(r!=n) rx=max(res1(1,n,r+1,n,1)-s[r],rx); an=max(an,lx+rx); } } cout<<ans+an<<endl; return 0; }