#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e5 + 69;
const ll mod = 1e9 + 7;
typedef pair<ll,ll> LL;
int dp[3300][3300],a[N],n,start,d;
ll Sub13(int n,int start,int d,int a[]){
multiset<ll> s;
ll ans = 0,lf = start - 1,rg = n - start,cur = 0,x = start;
for (ll i = 0;i <= lf;i++){
s.clear(); cur = 0;
for (ll j = 0;j <= i;j++) cur += a[x - j],s.insert(a[x - j]);
for (ll j = 0;j <= rg;j++){
ll rm = d - i - j - min(i,j);
if (j != 0) s.insert(a[x + j]),cur += a[x + j];
if (rm <= 0) continue;
while(s.size() > rm) cur -= *s.begin(),s.erase(s.begin());
//cout<<i<<" "<<j<<" "<<cur<<"\n";
ans = max(ans,cur);
}
}
return ans;
}
ll Sub2(int n,int start,int d,int a[]){
priority_queue<ll> pq;
ll cur = 0,ans = 0;
for (ll i = 1;i <= n;i++){
pq.push(a[i]); cur += a[i];
ll rm = max(0ll,d - i - 1);
while(pq.size() > rm){
cur -= pq.top(); pq.pop();
}
ans = max(ans,cur);
}
return ans;
}
ll findMaxAttraction(int n,int start,int d,int arr[]){
for (ll i = 0;i < n;i++) a[i + 1] = arr[i];
if (n <= 3000) return Sub13(n,start + 1,d,a);
else if (start == 0) return Sub2(n,start + 1,d,a);
}
/*
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>start>>d;
for (ll i = 1;i <= n;i++) cin>>a[i];
cout<<findMaxAttraction(n,start,d,a);
}
*/
