#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define all(v) v.begin(), v.end()
const int maxn = 7e3+100;
//#define int ll
#define pii pair <int, int>
int inf = 1e9;
ll a[3010], dp[3][7510][5], dl[7510][3], dr[7510][3];
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
ll ans = 0;
ll s = 0;
forn(1, i, n)
{
a[i] = attraction[i - 1];
}
start++;
forn(0, i, 1)
{
forn(0, j, d + 2)
{
forn(0, k, 3) dp[i][j][k] = -inf;
}
}
forn(0, j, 7500)
{
dl[j][0] = -inf;
dl[j][1] = -inf;
dr[j][0] = -inf;
dr[j][1] = -inf;
}
int p = 0;
dp[p][0][0] = 0;
dp[p][1][0] = a[start];
forn(start, i, n)
{
forn(0, j, d)
{
dr[j][0] = max(dr[j][0], dp[p][j][0]);
dp[p ^ 1][j + 1][0] = max(dp[p ^ 1][j + 1][0], dp[p][j][0]);
dp[p ^ 1][j + 2][0] = max(dp[p ^ 1][j + 2][0], dp[p][j][0] + a[i + 1]);
dp[p][j][0] = -inf;
}
p ^= 1;
}
p = 0;
dp[p][0][1] = 0;
forn(start, i, n)
{
forn(0, j, d)
{
dr[j][1] = max(dr[j][1], dp[p][j][1]);
dp[p ^ 1][j + 2][1] = max(dp[p ^ 1][j + 2][1], dp[p][j][1]);
dp[p ^ 1][j + 3][1] = max(dp[p ^ 1][j + 3][1], dp[p][j][1] + a[i + 1]);
dp[p][j][1] = -inf;
}
p ^= 1;
}
dp[p][0][2] = 0;
dp[p][1][2] = a[start];
nfor(1, i, start)
{
forn(0, j, d)
{
dl[j][0] = max(dl[j][0], dp[p][j][2]);
dp[p ^ 1][j + 1][2] = max(dp[p ^ 1][j + 1][2], dp[p][j][2]);
dp[p ^ 1][j + 2][2] = max(dp[p ^ 1][j + 2][2], dp[p][j][2] + a[i - 1]);
dp[p][j][2] = -inf;
}
p ^= 1;
}
dp[p][0][3] = 0;
nfor(1, i, start)
{
forn(0, j, d)
{
dl[j][1] = max(dl[j][1], dp[p][j][3]);
dp[p ^ 1][j + 2][3] = max(dp[p ^ 1][j + 2][3], dp[p][j][3]);
dp[p ^ 1][j + 3][3] = max(dp[p ^ 1][j + 3][3], dp[p][j][3] + a[i - 1]);
dp[p][j][3] = -inf;
}
p ^= 1;
}
forn(1, j, d)
{
dr[j][0] = max(dr[j][0], dr[j - 1][0]);
dr[j][1] = max(dr[j][1], dr[j - 1][1]);
dl[j][0] = max(dl[j][0], dl[j - 1][0]);
dl[j][1] = max(dl[j][1], dl[j - 1][1]);
}
forn(0, j, d)
{
ans = max(ans, dr[j][1] + dl[d - j][0]);
ans = max(ans, dr[j][0] + dl[d - j][1]);
ans = max(ans, dl[j][1] + dr[d - j][0]);
ans = max(ans, dl[j][0] + dr[d - j][1]);
}
return ans;
}
/*
int main() {
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}*/
