#include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e6 + 5; int n, k, x, ans; int a[N], s[N]; int tl, hd, q[N]; int he, ta, q2[N]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k >> x; if(x < 0) x = -x, k = n - k; for(int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i]; hd = 1; he = 1; q[++tl] = 0; for(int i = 1; i <= n; i++) { int val1 = s[i] + i * x, val2 = s[i] - i * x; while(i - q[hd] > k && hd <= tl) { while(s[q[hd]] - q[hd] * x <= s[q2[ta]] - q2[ta] * x && he <= ta) ta--; q2[++ta] = q[hd]; hd++; } if(hd <= tl) ans = max(ans, val1 - (s[q[hd]] + q[hd] * x)); if(he <= ta) ans = max(ans, val2 - (s[q2[he]] - q2[he] * x) + 2 * k * x); while(val1 <= s[q[tl]] + q[tl] * x && hd <= tl) tl--; q[++tl] = i; } cout << ans; return 0; }