#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,start,d;
int a[100005];
ll calc(int le, int ri)
{
assert(le<=start);
assert(ri>=start);
int ramase = d - (ri-le) - (ri-start);
vector<int> v;
for(int i=le;i<=ri;i++)
{
v.push_back(a[i]);
}
sort(v.begin(),v.end());
ramase = min(ramase, (int)v.size());
ll sum=0;
for(int i=1;i<=ramase;i++)
sum += v[(int)v.size()-i];
return sum;
}
ll solve()
{
ll mxm=0;
/*int le=1;
for(int ri=start;ri<=n;ri++)
{
while(le+1<=d && calc(le+1,ri) >= calc(le,ri))
le++;
mxm = max(mxm, calc(le,ri));
}*/
for(int le=start;le>0;le--)
for(int ri=start+1;ri<=n;ri++)
mxm = max(mxm, calc(le,ri));
return mxm;
}
ll findMaxAttraction(int cit_n, int cit_start, int cit_d, int cit_a[])
{
n = cit_n;
start = cit_start + 1;
d = cit_d;
for(int i=0;i<n;i++)
a[i+1] = cit_a[i];
ll idk = solve();
reverse(a+1,a+1+n);
start = n - start + 1;
idk = max(idk, solve());
return idk;
}
