#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long findMaxAttraction(int32_t n, int32_t s, int32_t d, int32_t arr[]) {
vector<vector<int>> left(d+1, vector<int>(d+1));
vector<vector<int>> right(d+1, vector<int>(d+1));
vector<int> bleft(d+1);
vector<int> bright(d+1);
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();
}
right[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();
}
left[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;
if(r < 0) break;
int c = 0;
c += left[l-steps][min(steps,l-steps)];
c += bright[r];
if(c > ans){
ans = c;
}
}
}
return ans;
}
