#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, K;
int A[100000];
long long int findMaxAttraction(int n, int index, int k, int a[])
{
N = n;
K = k;
for(int i = 0; i < N; i++) A[i] = a[i];
ll sol = 0;
auto Try = [&]()
{
for(int i = index; i >= 0; i--)
{
priority_queue <int> H;
ll sum = 0;
for(int j = index; j >= i; j--) {H.push(-A[j]); sum += A[j];}
while(H.size() && (H.size() > (K - (index - i)))) {sum += H.top(); H.pop();}
sol = max(sum, sol);
for(int j = index + 1; H.size() && (j < N); j++)
{
H.push(-A[j]);
sum += A[j];
while(H.size() && (H.size() > (K - (index - i + j - i)))) {sum += H.top(); H.pop();}
sol = max(sum, sol);
}
}
return;
};
Try();
if(N > 3000) return sol;
reverse(A, A + N);
index = N - index - 1;
Try();
return sol;
}
//int main()
//{
// int n, k, index;
// cin >> n >> k >> index;
// int a[n];
// for(int i = 0; i < n; i++) cin >> a[i];
// cout << findMaxAttraction(n, index, k, a) << '\n';
//}
