#include <bits/stdc++.h>
#ifndef DEBUG
#include "holiday.h"
#endif
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//===================//
// begin program //
//===================//
const int MX = 5e5;
const int N = (1<<17);
vi a, sa, ra;
int n, start, d;
// segment tree
ll TOT[N*2], SUM[N*2];
void setSeg(int i, ll v, int l=0, int r=N-1, int p=1) {
if(i < l || i > r) return;
if(l == r) {
TOT[p] = v ? 1 : 0;
SUM[p] = v;
return;
}
int m=(l+r)/2;
setSeg(i,v,l ,m,p*2 );
setSeg(i,v,m+1,r,p*2+1);
TOT[p] = TOT[p*2] + TOT[p*2+1];
SUM[p] = SUM[p*2] + SUM[p*2+1];
}
ll getSeg(int x, int l=0, int r=N-1, int p=1) {
if(x <= 0) return 0;
if(TOT[p] <= x) return SUM[p];
int m=(l+r)/2;
if(TOT[p*2+1] <= x) {
return SUM[p*2+1] + getSeg(x-TOT[p*2+1], l, m, p*2);
} else {
return getSeg(x, m+1, r, p*2+1);
}
}
void addX(int x) {
setSeg(ra[x],a[x]);
}
void removeX(int x) {
setSeg(ra[x],0);
}
ll daq(int l, int r, int al, int ar) {
// we currently have [l,al) in our segment tree
if(l > r) return 0;
int mid=(l+r)/2;
// make it so that we have [mid,al) in our segment tree
if(al < mid) {
REP(i,l,al) removeX(i);
} else {
REP(i,l,mid) removeX(i);
}
ll res=0, bestM=0;
REP(i,max(al,mid),ar+1) {
addX(i);
ll used = start + i - mid*2;
if(used >= d) break;
ll nRes = getSeg(d - used);
if(nRes > res) {
bestM = i;
res = nRes;
}
}
// turn it back so we have [l,al) again in our segment tree
if(al < mid) {
REP(i,mid,ar+1) removeX(i);
REP(i,l,al) addX(i);
} else {
REP(i,al,ar+1) removeX(i);
REP(i,l,al) addX(i);
}
res = max(res, daq(l,mid-1,al,bestM));
REP(i,al,bestM) addX(i);
REP(i,l,mid+1) removeX(i);
res = max(res, daq(mid+1,r,bestM,ar));
REP(i,al,bestM) removeX(i);
REP(i,l,mid+1) addX(i);
return res;
}
ll solve() {
sa.resize(n);
RE(i,n) sa[i]=i;
sort(all(sa),[](int i, int j) {
return a[i] < a[j];
});
ra.resize(n);
RE(i,n) ra[sa[i]] = i;
RE(i,N*2) TOT[i] = SUM[i] = 0;
return daq(0,start,0,n-1);
}
ll findMaxAttraction(int _n, int _start, int _d, int attraction[]) {
n = _n; start = _start; d = _d;
RE(i,n) a.pb(attraction[i]);
ll res = 0;
RE(_,2) {
res = max(res, solve());
// reverse everyrhing
start = n - start - 1;
reverse(all(a));
}
return res;
}
#ifdef DEBUG
int _n, D, Start, Att[100000];
int main() {
cin>>_n>>Start>>D;
RE(i,_n) cin>>Att[i];
cout<<findMaxAttraction(_n,Start,D,Att)<<endl;
}
#endif
