#include <bits/stdc++.h>
#ifndef LOCAL
#include <holiday.h>
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
const ll inf = 1e18;
const int MAXNODES = 4e6 + 5;
int lc[MAXNODES], rc[MAXNODES], cnt[MAXNODES], nNodes;
ll sum[MAXNODES];
int build(int l, int r){
if(l == r) return ++nNodes;
int o = ++nNodes, mid = l + r >> 1;
lc[o] = build(l, mid);
rc[o] = build(mid + 1, r);
return o;
}
vector<int> values;
void refine(int cur){
sum[cur] = sum[lc[cur]] + sum[rc[cur]];
cnt[cur] = cnt[lc[cur]] + cnt[rc[cur]];
}
int update(int p, int l, int r, int pos){
if(l == r){
int o = ++nNodes;
sum[o] = sum[p] + values[l];
cnt[o] = cnt[p] + 1;
return o;
}
int mid = l + r >> 1, o = ++nNodes;
if(pos <= mid){
lc[o] = update(lc[p], l, mid, pos);
rc[o] = rc[p];
refine(o);
} else{
lc[o] = lc[p];
rc[o] = update(rc[p], mid + 1, r, pos);
refine(o);
}
return o;
}
ll query(int pL, int pR, int l, int r, int k){
if(l == r) return 1LL * values[l] * min(cnt[pR] - cnt[pL], k);
int mid = l + r >> 1;
int rightHave = cnt[rc[pR]] - cnt[rc[pL]]; //prioritize right first
ll rightSum = sum[rc[pR]] - sum[rc[pL]];
if(k > rightHave) return rightSum + query(lc[pL], lc[pR], l, mid, k - rightHave);
else return query(rc[pL], rc[pR], mid + 1, r, k);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]){
++start;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i){
a[i] = attraction[i - 1];
values.push_back(a[i]);
}
sort(all(values));
compact(values);
for(int i = 1; i <= n; ++i){
a[i] = lower_bound(all(values), a[i]) - values.begin();
}
int m = sz(values) - 1;
ll ans = 0;
auto solve = [&](){
vector<int> roots;
roots.push_back(build(0, m));
for(int i = 1; i <= n; ++i){
roots.push_back(update(roots.back(), 0, m, a[i]));
}
auto query_cost = [&](int l, int r){
int moves = (r - l + min(r - start, start - l)); //choosing first direction
if(moves > d) return -inf;
int can_take = min(r - l + 1, d - moves);
ll ret = query(roots[l - 1], roots[r], 0, m, can_take);
return ret;
};
function<void(int, int, int, int)> dnc = [&](int l, int r, int optL, int optR){
int mid = l + r >> 1;
ll opt_value = -inf;
int opt_mid = optL;
for(int i = max(mid, optL); i <= optR; ++i){
if(maximize(opt_value, query_cost(mid, i))){
opt_mid = i;
}
}
ans = max(ans, opt_value);
if(l < mid) dnc(l, mid - 1, optL, opt_mid);
if(mid < r) dnc(mid + 1, r, opt_mid, optR);
};
dnc(1, start, start, n);
// auto check_valid = [&](){
// for(int i = 1; i <= start; ++i){
// ll opt_value = -inf;
// int opt_mid = -1;
// for(int j = start; j <= n; ++j){
// if(maximize(opt_value, query_cost(i, j))){
// opt_mid = j;
// }
// }
//
// cout << opt_mid << ' ';
// }
// cout << '\n';
// };
//
// check_valid();
// for(int i = 1; i <= start; ++i){
// for(int j = start; j <= n; ++j){
// maximize(ans, query_cost(i, j));
// }
// }
};
solve();
// reverse(a.begin() + 1, a.end());
// start = n - start + 1;
// solve();
return ans;
}
#ifdef LOCAL
int main(){
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int n, start, d;
cin >> n >> start >> d;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
cout << findMaxAttraction(n, start, d, a) << '\n';
return 0;
}
#endif
