#include <cstdio> #include <iostream> using namespace std; typedef long long ll; #define TYPE ll #define FOR(x,y,z) for (TYPE x = (y); x <= (z); x += 1) #define ROF(x,y,z) for (TYPE x = (z); x >= (y); x -= 1) #define FORR(x,y) FOR(x, 1, y) #define ROFF(x,y) ROF(x, y, 1) #define FORS(x,y) FOR(x, 0, (y) - 1) #define ROFS(x,y) ROF(x, (y) - 1, 0) // {{{ OI TYPE read() { TYPE x=0,f=1;char h=getchar(); while(!(h>='0'&&h<='9')){if(h=='-')f=-f;h=getchar();} while(h>='0'&&h<='9'){x=x*10+int(h-'0');h=getchar();} return x*f; } struct OI { OI operator >> (TYPE& x) const { x = read(); return *this; } } oi; // }}} const int N = 2e5 + 500; ll n, k, x; ll a[N], s[N]; bool vis[N]; ll dfs(int depth, int last, int cnt) { if (depth == k + 1) { if (cnt != k) return 0; ll ans = 0; s[0] = 0; FORR(i, n) { s[i] = s[i - 1] + a[i]; if (vis[i]) s[i] += x; else s[i] -= x; // cout << a[i] + (vis[i] ? x : -x) << " "; } // cout << "-> "; FORR(i, n) FOR(j, i, n) { ans = max(ans, s[j] - s[i - 1]); } // cout << ans << endl; return ans; } if (cnt > k) return 0; if (cnt == k) return max(0ll, dfs(depth + 1, last, cnt)); ll res = 0; FOR(i, last + 1, n) { if (vis[i]) continue; vis[i] = true; res = max(res, dfs(depth + 1, i, cnt + 1)); vis[i] = false; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("d.in", "r", stdin); oi >> n >> k >> x; FORR(i, n) { oi >> a[i]; s[i] = s[i - 1] + a[i]; } if (k == 0) { ll ans = 0; FORR(i, n) FOR(j, i, n) ans = max(ans, s[j] - s[i - 1]); cout << ans << endl; return 0; } cout << dfs(1, 0, 0) << endl; return 0; }