#ifndef SUN
#include "holiday.h"
#endif // SUN
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl
#define left __left
#define right __right
#define prev __prev
#define fi first
#define se second
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
int numPlace, start, days;
#define MAX_N 100'100
int a[MAX_N + 2];
namespace subtask1 {
bool check() {
return (numPlace <= 20);
}
ll solve() {
ll ans = 0;
FOR(mask, 0, MASK(numPlace) - 1) {
if (BIT(mask, start) == 0) continue;
int minBit = -1, maxBit = -1; /// position;
int numBit = 0;
ll res = 0;
FOR(i, 0, numPlace - 1) {
if (BIT(mask, i)) {
++numBit;
maxBit = i;
if (minBit == -1) minBit = i;
res += a[i];
}
}
if (numBit + maxBit - minBit + min(maxBit - start, start - minBit) <= days) {
maximize(ans, res);
}
/// case2: don't visit at start;
numBit--;
res -= a[start];
if (numBit + maxBit - minBit + min(maxBit - start, start - minBit) <= days) {
maximize(ans, res);
}
}
return ans;
}
}
namespace subtask2 {
bool check() {
return (start == 0 && *max_element(a, a + numPlace) <= 100);
}
int cnt[102];
ll solve() {
/// move from 0 .. i with i < numPlace: cost = i;
/// thi luc do la days -= i; roi tim sum_element of day;
ll ans = 0;
FOR(i, 0, numPlace - 1) {
assert(a[i] <= 100);
cnt[a[i]]++;
int tmp_d = days - i;
if (tmp_d <= 0) break;
ll res = 0;
FORD(val, 100, 1) {
if (cnt[val] >= tmp_d) {
res += tmp_d * val;
break;
} else {
res += cnt[val] * val;
tmp_d -= cnt[val];
}
}
maximize(ans, res);
}
return ans;
}
}
namespace subtask3 {
bool check() {
return (numPlace <= 3000);
}
#define LIM 3030
ll dp[LIM + 2][7520];
ll revDp[LIM + 2][7520];
int id[LIM + 2];
struct SEGTREE {
ll seg[4 * LIM + 2];
int cnt[4 * LIM + 2];
void update(int id, int l, int r, int pos, int val, int mul) {
while (l < r) {
int g = (l + r) >> 1;
if (pos <= g) {
r = g;
id = 2 * id;
} else {
l = g + 1;
id = 2 * id + 1;
}
}
seg[id] += val;
cnt[id] += mul;
while (id > 1) {
id >>= 1;
seg[id] = seg[id << 1] + seg[id << 1 | 1];
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
}
/// tim vi tri be nhat sao cho sumCnt tu n .. i <= val;
// ll walk(int id, int l, int r, int val) {
// if (cnt[id] <= val) return seg[id];
//
// int g = (l + r) >> 1;
// if (cnt[id << 1 | 1] >= val) return walk(id << 1 | 1, g + 1, r, val);
// return walk(id << 1, l, g, r, val - cnt[id << 1 | 1]) + seg[id << 1 | 1];
// }
void update(int pos, int val, int mul) {
update(1, 1, numPlace, pos, val, mul);
}
int getCnt(int id, int l, int r, int u, int v) {
if (l > v || u > r) return 0;
if (u <= l && r <= v) return cnt[id];
int g = (l + r) >> 1;
return getCnt(id << 1, l, g, u, v) + getCnt(id << 1 | 1, g + 1, r, u, v);
}
ll get(int id, int l, int r, int u, int v) {
if (l > v || u > r) return 0;
if (u <= l && r <= v) return seg[id];
int g = (l + r) >> 1;
return get(id << 1, l, g, u, v) + get(id << 1 | 1, g + 1, r, u, v);
}
} st;
int POS(int x, const vector <int> &v) {
return lower_bound(ALL(v), x) - v.begin() + 1;
}
ll solve() {
vector <int> vec;
FOR(i, 0, numPlace - 1) vec.push_back(a[i]);
sort(ALL(vec));
vec.erase(unique(ALL(vec)), vec.end());
FOR(i, 0, numPlace - 1) id[i] = POS(a[i], vec);
// dp[i][j]: xet i .. j: maxCost = ...;
ll ans = 0;
FORD(i, start, 0) {
st.update(id[i], a[i], 1);
FOR(j, start, numPlace - 1) {
int tmp_d = days - (j - i + min(j - start, start - i));
if (tmp_d <= 0) break;
if (j != start) st.update(id[j], a[j], 1);
ll res = 0;
if (j - i + 1 <= tmp_d) res = st.get(1, 1, numPlace, 1, numPlace);
else {
int l = 1, r = numPlace, g, vt = -1, dem = 0;
while (l <= r) {
g = (l + r) >> 1;
int d = st.getCnt(1, 1, numPlace, g, numPlace);
if (d >= tmp_d) {
vt = g, dem = d;
l = g + 1;
} else {
r = g - 1;
}
}
res = st.get(1, 1, numPlace, vt, numPlace) - (dem - tmp_d) * vec[vt - 1];
}
maximize(ans, res);
}
FOR(j, start, numPlace - 1) {
int tmp_d = days - (j - i + min(j - start, start - i));
if (tmp_d <= 0) break;
if (j != start) st.update(id[j], -a[j], -1);
}
}
return ans;
}
}
long long int findMaxAttraction(int __n, int __start, int __d, int attraction[]) {
numPlace = __n;
start = __start;
days = __d;
FOR(i, 0, numPlace - 1) a[i] = attraction[i];
if (subtask1 :: check()) return subtask1 :: solve();
if (subtask2 :: check()) return subtask2 :: solve();
if (subtask3 :: check()) return subtask3 :: solve();
}
#ifdef SUN
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
cin >> numPlace >> start >> days;
FOR(i, 0, numPlace - 1) cin >> a[i];
cout << findMaxAttraction(numPlace, start, days, a);
return 0;
}
#endif // SUN
/* Discipline - Calm */
