#include<bits/stdc++.h> using namespace std; const int N =5001; const int Maxn=1e5+10; #define int long long int a[N],dp[N][N],DP[Maxn][21],n,k,x,ans; void Slove1(){ for(int i=1;i<=n;i++) cin>>a[i],a[i]+=x; k=n-k; for(int i=1;i<=n;i++){ DP[i][0]=max((long long)0,DP[i-1][0]+a[i]); if(i+(k-0)<=n) ans=max(ans,DP[i][0]); for(int j=1;j<=min(i,k);j++){ if(j==i){ DP[i][j]=max(DP[i][j],DP[i-1][j-1]+a[i]+2*(-x)); if(i+(k-j)<=n) ans=max(ans,DP[i][j]); } else{ if(i-1>=j){ DP[i][j]=max(DP[i][j],DP[i-1][j]+a[i]); if(i+(k-j)<=n) ans=max(ans,DP[i][j]); } DP[i][j]=max(DP[i][j],DP[i-1][j-1]+a[i]+2*(-x)); if(i+(k-j)<=n) ans=max(ans,DP[i][j]); } } } cout<<max((long long)0,ans)<<endl; } signed main(){ cin>>n>>k>>x; if(n-k<=20) Slove1(),exit(0); for(int i=1;i<=n;i++) cin>>a[i],a[i]-=x; // memset(dp,-0x3f,sizeof(dp)); for(int i=1;i<=n;i++){ dp[i][0]=max((long long)0,dp[i-1][0]+a[i]); if(i+(k-0)<=n) ans=max(ans,dp[i][0]); for(int j=1;j<=min(i,k);j++){ if(j==i){ dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]+2*x); if(i+(k-j)<=n) ans=max(ans,dp[i][j]); // dp[i][j]=max(dp[i][j],0); } else{ if(i-1>=j){ dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i]); if(i+(k-j)<=n) ans=max(ans,dp[i][j]); } dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]+2*x); if(i+(k-j)<=n) ans=max(ans,dp[i][j]); } } } cout<<max((long long)0,ans)<<endl; }