#include <bits/stdc++.h>
using namespace std;
template<typename T, typename Cmp = less<T>>
struct max_sum_set
{
Cmp cmp;
vector<T> values;
void insert(const T& x)
{
values.push_back(x);
}
T get(size_t k)
{
nth_element(values.begin(), values.begin() + k, values.end(), cmp);
return accumulate(values.begin(), values.begin() + k, T(0));
}
};
vector<int64_t> best_values(const vector<int>& A)
{
max_sum_set<int64_t, greater<int64_t>> val;
vector<int64_t> result(2*A.size());
for(size_t p = 1; p <= A.size(); p++)
{
val.insert(A[p - 1]);
for(size_t q = 1; q <= p; q++)
result[p + q] = max(result[p + q], val.get(q));
}
return result;
}
int64_t solve_right(const vector<int>& A, size_t s, size_t d)
{
auto R = best_values(vector<int>(A.begin() + s, A.end())),
L = best_values(vector<int>(A.rbegin() + (A.size()-s), A.rend()));
int64_t result = 0;
for(size_t r = 0; r <= d + 1; r++)
{
size_t l = (d - r + 1) / 2;
result = max(result, L[l] + R[r]);
}
return result;
}
long long int findMaxAttraction(int n, int start, int d, int a[])
{
vector<int> A(a, a + n);
int64_t result = solve_right(A, start, d);
reverse(A.begin(), A.end());
result = max(result, solve_right(A, n-1 - start, d));
return result;
}
