#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "holiday.h"
#endif
using namespace std;
using ll=long long;
ll findMaxAttraction(int n, int sta, int d, int A[])
{
ll global_ans=0LL;
for(int r=sta; r<n; r++)
{
ll ans=0LL;
priority_queue<ll> active;
ll active_sum=0LL;
for(int i=sta+1; i<=r; i++)
{
active_sum += ll(A[i]);
active.push(ll(-A[i]));
}
for(int i=sta; i>=0; i--)
{
active.push(ll(-A[i]));
active_sum += ll(A[i]);
// cout << 2*(r-sta) + sta-i << endl;
while(int(active.size()) + 2*(r-sta) + sta-i > d && !active.empty())
{
active_sum += active.top();
active.pop();
}
if(int(active.size()) + 2*(r-sta) + sta-i <= d) ans = max(ans,active_sum);
}
global_ans = max(global_ans,ans);
// cout << r << " " << ans << endl;
}
// reverse that shit afterwards
int B[n];
for(int i=0; i<n; i++) B[i]=A[n-i-1];
sta = n-sta-1;
for(int r=sta; r<n; r++)
{
ll ans=0LL;
priority_queue<ll> active;
ll active_sum=0LL;
for(int i=sta+1; i<=r; i++)
{
active_sum += ll(B[i]);
active.push(ll(-B[i]));
}
for(int i=sta; i>=0; i--)
{
active.push(ll(-B[i]));
active_sum += ll(B[i]);
// cout << 2*(r-sta) + sta-i << endl;
while(int(active.size()) + 2*(r-sta) + sta-i > d && !active.empty())
{
active_sum += active.top();
active.pop();
}
if(int(active.size()) + 2*(r-sta) + sta-i <= d) ans = max(ans,active_sum);
}
global_ans = max(global_ans,ans);
// cout << r << " " << ans << endl;
}
return global_ans;
}
