#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; long long a[MAXN], f1[MAXN], f2[MAXN]; long long ans = 0; int n, k; long long x; int cnt1, cnt2, cnt3; void shit(int l, int r) { if (l == r) { ans = max(ans, (k > 0) ? (a[l] + x) : a[l]); return; } int mid = l + r >> 1; shit(l, mid), shit(mid + 1, r); long long sum = a[mid], maxx1 = a[mid]; int maxi1 = mid; for (int i = mid - 1; i >= l; --i) { sum += a[i]; if (sum > maxx1) maxx1 = sum, maxi1 = i; } sum = a[mid + 1]; long long maxx2 = sum; int maxi2 = mid + 1; for (int i = mid + 2; i <= r; ++i) { sum += a[i]; if (sum > maxx2) maxx2 = sum, maxi2 = i; } if (maxi2 - maxi1 + 1 >= k) { ans = max(ans, maxx1 + maxx2 + k * x); ++cnt1; return; } sum = a[mid] + x, maxx1 = sum, maxi1 = mid; for (int i = mid - 1, j = 0; i >= l && j < k; --i, ++j) { sum += a[i] + x; if (sum > maxx1) maxx1 = sum, maxi1 = i; } sum = a[mid + 1] + x, maxx2 = sum, maxi2 = mid + 1; for (int i = mid + 2, j = 0; i <= r && j < k; ++i, ++j) { sum += a[i] + x; if (sum > maxx2) maxx2 = sum, maxi2 = i; } if (maxi2 - maxi1 + 1 <= k) { ans = max(ans, maxx1 + maxx2); ++cnt2; return; } ++cnt3; int ll = max(mid - k + 1, l), rr = mid; sum = 0; for (int i = ll; i <= rr; ++i) { sum += a[i] + x; } // int nl = -1, nr; while (ll <= mid) { while (a[ll] + x <= 0 && ll <= mid) { sum -= a[ll] + x; ++ll; } long long xxx = sum + (ll > 0 ? f1[ll - 1] : 0) + (rr + 1 < n ? f2[rr + 1] : 0); if (ans < xxx) ans = xxx; while (rr - ll + 1 < k && rr < r) { ++rr; sum += a[rr] + x; long long xxx = sum + (ll > 0 ? f1[ll - 1] : 0) + (rr + 1 < n ? f2[rr + 1] : 0); if (ans < xxx) ans = xxx; } sum -= a[ll] + x; ++ll; } // if (nl > -1) { // while (nl > l && a[nl - 1] > 0) { // --nl; // ans += a[nl]; // } // while (nr < r && a[nr + 1] > 0) { // ++nr; // ans += a[nr]; // } // } // cout << nl << ' ' << nr << ' ' << mid << '\n'; } int main() { // freopen("T2.in", "r", stdin); // freopen("T2.out", "w", stdout); cin >> n >> k >> x; if (x < 0) { k = n - k; x = -x; } for (int i = 0; i < n; ++i) { cin >> a[i]; a[i] -= x; } long long sum = 0; for (int i = 0; i < n; ++i) { if (sum + a[i] > 0) { sum += a[i]; } else { sum = 0; } f1[i] = sum; // cout << f1[i] << ' '; } sum = 0; for (int i = n - 1; i > -1; --i) { if (sum + a[i] > 0) { sum += a[i]; } else { sum = 0; } f2[i] = sum; } // cout << '\n'; // for (int i = 0; i < n; ++i) { // cout << f2[i] << ' '; // } // cout << '\n'; x <<= 1; shit(0, n - 1); cout << ans; // cout << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3; return 0; }