#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; long long a[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; } while (ll <= mid) { while (a[ll] + x <= 0 && ll <= mid) { sum -= a[ll] + x; ++ll; } ans = max(ans, sum); if (a[rr + 1] + x >= 0) { while (a[rr + 1] + x >= 0 && rr - ll + 1 < k && rr < r) { ++rr; sum += a[rr] + x; ans = max(ans, sum); } } else { while (a[rr + 1] + x < 0 && rr - ll + 1 < k && rr < r) { ++rr; sum += a[rr] + x; ans = max(ans, sum); } while (a[rr + 1] + x >= 0 && rr - ll + 1 < k && rr < r) { ++rr; sum += a[rr] + x; ans = max(ans, sum); } } sum -= a[ll] + x; ++ll; } } 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; } x <<= 1; shit(0, n - 1); cout << ans; // cout << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3; return 0; }