#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
ll DP[3005][10000][2], dp[3005][10000][2];
ll solve(ll i, ll K, ll add, ll N, ll S, ll D, int C[]) {
if(i < 0 || i == N || K <= 0) return 0;
if(DP[i][K][add] != -1) return DP[i][K][add];
if(add == 0) {
ll A = solve(i - 1, K - 1, add, N, S, D, C);
ll B = C[i] + solve(i - 1, K - 2, add, N, S, D, C);
ll U = solve(S + 1, K - (S - i + 1), 1 - add, N, S, D, C);
ll V = C[i] + solve(S + 1, K - (S - i + 1) - 1, 1 - add, N, S, D, C);
return DP[i][K][add] = max({A, B, U, V});
}
if(add == 1) {
ll A = solve(i + 1, K - 1, add, N, S, D, C);
ll B = C[i] + solve(i + 1, K - 2, add, N, S, D, C);
return DP[i][K][add] = max({A, B});
}
return 0;
}
ll Solve(ll i, ll K, ll add, ll N, ll S, ll D, int C[]) {
if(i < 0 || i == N || K <= 0) return 0;
if(dp[i][K][add] != -1) return dp[i][K][add];
if(add == 0) {
ll A = Solve(i + 1, K - 1, add, N, S, D, C);
ll B = C[i] + Solve(i + 1, K - 2, add, N, S, D, C);
ll U = Solve(S - 1, K - (i - S + 1), 1 - add, N, S, D, C);
ll V = C[i] + Solve(S - 1, K - (i - S + 1) - 1, 1 - add, N, S, D, C);
return dp[i][K][add] = max({A, B, U, V});
}
if(add == 1) {
ll A = Solve(i - 1, K - 1, add, N, S, D, C);
ll B = C[i] + Solve(i - 1, K - 2, add, N, S, D, C);
return dp[i][K][add] = max({A, B});
}
return 0;
}
ll findMaxAttraction(int N, int start, int D, int attraction[]) {
memset(DP, -1, sizeof DP);
memset(dp, -1, sizeof dp);
ll A = solve(start, D, 0, N, start, D, attraction);
ll B = Solve(start, D, 0, N, start, D, attraction);
return max(A, B);
}
