#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
using ll = long long;
constexpr int MAXN = 5+3000;
long long memo[2][MAXN][2*MAXN+(MAXN/2)];
vector<int> a;
long long dp(int i, int d) {
if (i >= (int)a.size() || d <= 0) return 0;
long long& ans = memo[0][i][d];
if (ans != -1) return ans;
return ans = max(a[i]+dp(1+i,d-2), dp(1+i,d-1));
}
long long dp2(int i, int d) {
if (i < 0 || d <= 0) return 0;
long long& ans = memo[1][i][d];
if (ans != -1) return ans;
return ans = max(a[i]+dp2(i-1,d-2), dp2(i-1,d-1));
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
a.resize(n);
for (int i = 0; i < n; ++i) a[i] = attraction[i];
long long ans = 0;
if (n <= 4000) { // Subtask 1,3.
memset(memo, -1, sizeof memo);
for (int i = start; i >= 0; --i) {
ans = max(ans, dp(i,d-abs(start-i)));
}
for (int i = start; i < n; ++i) {
ans = max(ans, dp2(i,d-abs(start-i)));
}
} else {
if (start == 0) { //Subtask 2.
vector<int> cnt(101,0);
for (int i = 0; i < n; ++i) {
cnt[a[i]]++;
int rem = d-i;
long long r = 0;
for (int j = 100; j >= 1 && rem >= 1; --j) {
if (cnt[j] >= rem) {
r += (1LL*rem*j);
rem = 0;
} else {
r += (1LL*cnt[j]*j);
rem -= cnt[j];
}
}
ans = max(ans, r);
}
} else {
assert(false); // Subtask 4.
}
}
return ans;
}
