//#include"holiday.h"
//#include <bits/stdc++.h>
//
//using namespace std;
//const int N=3055;
//long long dp[N][N*3];
//int last[N][N*3];
//int a[N];
//int n;
//
//long long bt(int i , int d , int val)
//{
// if(d<=0)
// return 0;
// if(dp[i][d]!=-1)
// return dp[i][d];
// if(d==1)
// {
// dp[i][d]=a[i];
// last[i][d]=i;
// return dp[i][d];
// }
// long long ret=0;
// if(i+val<n&&i+val>=0)
// {
// ret=max(bt(i+val,d-1,val),ret);
// if(ret>bt(i+val,d-2,val)+a[i])
// {
// ret=max(bt(i+val,d-2,val)+a[i],ret);
// last[i][d]=last[i+val][d-2];
// }
// else
// last[i][d]=last[i+val][d-1];
// }
// dp[i][d]=ret;
// return ret;
//}
//
//
//long long int findMaxAttraction(int m, int start, int d, int ar[])
//{
// memset(dp,-1,sizeof dp);
// n=m;
// for(int i=0;i<n;i++)
// a[i]=ar[i];
// long long ret=0;
// for(int i=d;i>=0;i--)
// {
// ret=max(bt(start-1,i,-1)+bt(start,d-(start-last[start][i])-i,+1),ret);
// }
// return ret;
//}
//
//int main() {
// int n, start, d;
// int attraction[100000];
// int i, n_s;
// n_s = scanf("%d %d %d", &n, &start, &d);
// for (i = 0 ; i < n; ++i) {
// n_s = scanf("%d", &attraction[i]);
// }
// printf("%lld\n", findMaxAttraction(n, start, d, attraction));
// return 0;
//}
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
priority_queue < int , vector < int > , greater < int > > pq;
const int N=3055;
long long int findMaxAttraction(int n, int start, int d, int a[])
{
if(!d)
return 0;
int x;
long long ret=0;
for(int j=0;j<=d;j++)
{
long long ans=0;
int last=start;
pq.push(a[start]);
ans+=a[start];
int y=j;
y--;
x=y/2;
for(int i=start+1;i<=x+start&&i<n;i++)
{
pq.push(a[i]);
ans+=a[i];
last=i;
}
bool q=y%2;
long long best=ans;
for(int i=x+1+start;i<n&&pq.size();i++)
{
if(!q)
{
ans-=pq.top();
pq.pop();
}
else
q=0;
if(pq.size()&&a[i]>pq.top())
{
ans+=a[i]-pq.top();
pq.pop();
if(ans>best)
{
best=ans;
last=i;
}
pq.push(a[i]);
}
}
while(pq.size())
pq.pop();
y=d-(last-start)-j;
if(y==0)
x=0;
else
x=y/2;
ans=0;
for(int i=start-1;i>=0&&i>start-x-1;i--)
{
if(y<=0)
break ;
pq.push(a[i]);
ans+=a[i];
}
long long best1=ans;
q=y%2;
for(int i=start-x-1;i>=0;i--)
{
if(y<=0)
break ;
if(!q)
{
ans-=pq.top();
pq.pop();
}
else
q=0;
if(pq.size()&&a[i]>pq.top())
{
ans+=a[i]-pq.top();
pq.pop();
if(ans>best1)
{
best1=ans;
}
pq.push(a[i]);
}
}
ret=max(best+best1,ret);
// cout<<best<<' '<<best1<<' '<<j<<endl;
while(pq.size())
pq.pop();
}
return ret;
}
//int main() {
// int n, start, d;
// int attraction[100000];
// int i, n_s;
// n_s = scanf("%d %d %d", &n, &start, &d);
// for (i = 0 ; i < n; ++i) {
// n_s = scanf("%d", &attraction[i]);
// }
// printf("%lld\n", findMaxAttraction(n, start, d, attraction));
// return 0;
//}
