#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
int L[8000][8000];
int R[8000][8000];
int bleft[8000];
int bright[8000];
int solve(int n, int s, int d, vector<int> arr){
int best = 0;
for(int k = 0; k <= d; k++){
int sum = 0;
int ma = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = s; i < n; i++){
sum += arr[i];
int len = i-s;
pq.push(arr[i]);
if(len > k) break;
while(len+pq.size() > k){
sum -= pq.top();
pq.pop();
}
R[k][len] = sum;
ma = max(ma,sum);
}
bright[k] = ma;
}
if(s == 0){
return bright[d];
}
s--;
for(int k = 0; k <= d; k++){
int sum = 0;
int ma = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = s; i >= 0; i--){
sum += arr[i];
int len = s-i;
pq.push(arr[i]);
if(len > k) break;
while(len+pq.size() > k){
sum -= pq.top();
pq.pop();
}
L[k][len] = sum;
ma = max(ma,sum);
}
bleft[k] = ma;
}
int ans = 0;
for(int l = 0; l <= d; l++){
for(int steps = 0; steps <= l; steps++){
int r = d-l-steps-1;
if(r < 0) break;
int c = 0;
c += R[l][min(steps,l)];
c += bleft[r];
if(c > ans){
ans = c;
}
}
}
return ans;
}
long long findMaxAttraction(int32_t n, int32_t s, int32_t d, int32_t A[]) {
vector<int> arr(n);
for(int i = 0; i < n; i++){
arr[i] = A[i];
}
int v1 = 0;
v1 = solve(n,s,d,arr);
reverse(arr.begin(),arr.end());
s = (n-1)-s;
int v2 = 0;
v2 = solve(n,s,d,arr);
return max(v1,v2);
}
