#include <bits/stdc++.h>
using namespace std;
vector<long long> in;
long long n,d,start;
void r(){
reverse(in.begin(),in.end()) , start = n-start-1;
}
long long solve3(){
long long d2 = d-1 , ret = in[start] , sum = ret;
multiset<long long> ms;
ms.insert(in[start]);
for(long long i = start+1 ; i < n ; i += 1){
d2 -= 1;
if(d2 < 0){
d2 += 1;
if(ms.size() == 0){
return ret;
}
sum -= *ms.begin();
ms.erase(ms.begin());
}
if(d2){
d2 -= 1;
sum += in[i];
ms.insert(in[i]);
}else if(ms.size() && in[i] > *ms.begin()){
sum -= *ms.begin();
ms.erase(ms.begin());
sum += in[i];
ms.insert(in[i]);
}
ret = max(ret,sum);
}
return ret;
}
long long solve2(){
long long ret = solve3();
r();
ret = max(ret,solve3());
r();
return ret;
}
long long solve(){
long long ret = 0;
for(long long l = 0 ; l < start ; l += 1){
if(2*(start-l) > d){
continue;
}
long long d2 = d-2*(start-l) , sum = 0;
multiset<long long> ms;
for(long long i = l ; i <= start ; i += 1){
if(d2){
d2 -= 1;
sum += in[i];
ms.insert(in[i]);
}else if(ms.size() && in[i] > *ms.begin()){
sum -= *ms.begin();
ms.erase(ms.begin());
sum += in[i];
ms.insert(in[i]);
}
ret = max(ret,sum);
}
for(long long i = start+1 ; i < n ; i += 1){
if(ms.size() == 0 && d2 == 0){
break;
}
d2 -= 1;
if(d2 < 0){
d2 += 1;
sum -= *ms.begin();
ms.erase(ms.begin());
}
if(d2){
d2 -= 1;
sum += in[i];
ms.insert(in[i]);
}else if(ms.size() && in[i] > *ms.begin()){
sum -= *ms.begin();
ms.erase(ms.begin());
sum += in[i];
ms.insert(in[i]);
}
ret = max(ret,sum);
}
}
return ret;
}
long long int findMaxAttraction(int N , int Start , int D , int attraction[]){
n = N , start = Start , d = D;
if(d == 0){
return 0;
}
for(int i = 0 ; i < n ; i += 1){
in.push_back(attraction[i]);
}
long long ret = solve2();
if(start == 0){
return ret;
}
ret = max(ret,solve());
r();
ret = max(ret,solve());
return ret;
}
