#include <bits/stdc++.h>
#include "holiday.h"
#define lp(i,a,b) for(int i=a;i<b;i ++)
#define MAXN 3005
#define pb push_back
#define pii pair<int,int>
#define ss second
#define ff first
#define lli long long int
using namespace std;
multiset<int> m ;
lli resp ;
int last ;
void tira()
{
resp -= *m.begin() ;
m.erase(m.begin()) ;
}
lli calc (int n, int start, int d,int a[], int v)
{
resp = 0 ;
m.clear() ;
lli best = -1 ;
for(int i = start ; i < min(n,start+d) and i > max(start-d , -1 ) ; i += v)
{
m.insert(a[i]) ;
resp += a[i] ;
int k = m.size() ;
if( k - 1 > d - abs(i - start) )
tira() ;
if(k > d - abs(i - start) ) tira() ;
if( best < resp )
{
best = resp ;
last = i ;
}
}
return best ;
}
long long int findMaxAttraction(int n, int start, int d,int a[])
{
if(start == 0) return calc(n,0,d,a,1) ;
lli best = -1;
lp(i,1,d+1)
{
lli ans ;
//
ans = calc(n, start , i , a , -1 ) ;
if( d - i - start + last - 1 > 0 ) ans += calc( n, start+1 , d - i - start + last - 1 , a , 1 ) ;
best = max(best, ans) ;
//
//
ans = calc(n, start , i ,a,1) ;
if( d - i - last + start -1 > 0 ) ans += calc(n,start-1 , d-i-last+start - 1 , a , -1);
best = max(best, ans) ;
}
return best ;
}
