#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, d;
int a[N];
long long solve(int s, int d) {
if (d <= 0) return 0ll;
priority_queue<int, vector<int>, greater<int>> pq;
long long sum = 0;
long long res = 0;
for (int i = s; i < n; i++) {
sum += a[i];
pq.push(a[i]);
while (!pq.empty() && (int)pq.size() > d - i + s) {
sum -= pq.top();
pq.pop();
}
res = max(res, sum);
}
return res;
}
long long findMaxAttraction(int _n, int start, int _d, int _attraction[]) {
n = _n;
for (int i = 0; i < n; i++)
a[i] = _attraction[i];
d = _d;
if (start == 0)
return solve(0, d);
long long res = 0;
for (int it = 0; it < 2; it++) {
for (int i = start; i >= 0; i--) {
res = max(res, solve(i, d - start + i));
}
reverse(a, a + n);
start = n - 1 - start;
}
return res;
}
