#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
using ll = long long;
constexpr int MAXN = 5+3000;
constexpr int MAXD = 5+2*MAXN+(MAXN/2);
long long dp[2][2][MAXD];
long long findMaxAttraction(int n, int start, int days, int attraction[]) {
long long res = 0;
if (n <= 3000) { // Subtask 1,3.
for (int i = n; i >= 0; --i) {
int b = i&1, l = b^1;
for (int d = 0; d < MAXD; ++d) {
long long& ans = dp[0][b][d] = 0;
if (i >= n || d == 0) continue;
if (d == 1) {
ans = max(dp[0][l][d-1], 1LL*attraction[i]);
} else {
assert(d >= 2);
ans = max(dp[0][l][d-2]+attraction[i], dp[0][l][d-1]);
}
}
if (i <= start && days-abs(i-start) >= 0) {
res = max(res, dp[0][b][days-abs(i-start)]);
}
}
for (int i = 0; i < n; ++i) {
int b = i&1, l = b^1;
for (int d = 0; d < MAXD; ++d) {
long long& ans = dp[1][b][d] = 0;
if (d == 0) continue;
if (i == 0) {
ans = attraction[i];
continue;
}
if (d == 1) {
ans = max(dp[1][l][d-1], 1LL*attraction[i]);
} else {
assert(d >= 2);
ans = max(dp[1][l][d-2]+attraction[i], dp[1][l][d-1]);
}
}
if (i >= start && days-abs(i-start) >= 0) {
res = max(res, dp[1][b][days-abs(i-start)]);
}
}
} else {
if (start == 0) { //Subtask 2.
vector<int> cnt(101,0);
for (int i = 0; i < n; ++i) {
cnt[attraction[i]]++;
int rem = days-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];
}
}
res = max(res, r);
}
}/* else {
assert(false); // Subtask 4.
}*/
}
return res;
}
