#include <bits/stdc++.h>
#include"holiday.h"
#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define far0(i, n) for(int i = int(n) - 1; i >= 0; -- i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
using namespace std;
typedef long long ll;
priority_queue<int> pq;
const int maxn = 20;
const int maxd = 2 * maxn + maxn / 2;
ll dp[maxn][maxd + 2];
ll tabla[maxd + 2];
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
ll res = 0, aux = 0;
int cantidad, aux2;
if(!start){
for0(i, n){
aux += (ll) attraction[i];
pq.push(-1 * attraction[i]);
cantidad = max(d - i, 0);
if(cantidad == 0){
break;
}
while((int) pq.size() > cantidad){
aux2 = pq.top();
pq.pop();
aux -= (ll) aux2 * -1LL;
}
res = max(res, aux);
}
return res;
}
if(start == n - 1){
far0(i, n){
aux += (ll) attraction[i];
pq.push(-1 * attraction[i]);
cantidad = max(d - (n - i - 1), 0);
if(cantidad == 0){
break;
}
while((int) pq.size() > cantidad){
aux2 = pq.top();
pq.pop();
aux -= (ll) aux2 * -1LL;
}
res = max(res, aux);
}
return res;
}
if(!d){
return 0;
}
if(n <= maxn){
dp[start - 1][1] = (ll) attraction[start - 1];
tabla[1] = dp[start - 1][1];
int maximo = 1;
far0(i, start - 1){
forn(j, start - 1 - i, (start - 1 - i) * 2){
dp[i][j] = max(dp[i + 1][j - 1], dp[i][j]);
dp[i][j + 1] = max(dp[i][j + 1], dp[i + 1][j - 1] + (ll) attraction[i]);
tabla[j] = max(tabla[j], dp[i][j]);
tabla[j + 1] = max(tabla[j + 1], dp[i][j + 1]);
maximo = max(maximo, j + 1);
}
}
dp[start][1] = (ll) attraction[start];
res = max(res, tabla[max(min(maximo, d - 1), 0)]);
res = max(res, tabla[max(min(maximo, d - 2), 0)] + dp[start][1]);
forn(i, start + 1, n - 1){
forn(j, i - start, (i - start) * 2){
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j - 1] + (ll) attraction[i]);
if(j <= d){
res = max(res, dp[i][j]);
res = max(res, dp[i][j] + tabla[max(min(maximo, d - j - (i - start + 1)), 0)]);
}
if(j + 1 <= d){
res = max(res, dp[i][j + 1]);
res = max(res, dp[i][j + 1] + tabla[max(min(maximo, d - (j + 1) - (i - start + 1)), 0)]);
}
}
}
for0(i, maxd + 2){
tabla[i] = 0;
}
for0(i, maxn){
for0(j, maxd + 2){
dp[i][j] = 0;
}
}
dp[start + 1][1] = (ll) attraction[start + 1];
tabla[1] = dp[start + 1][1];
maximo = 1;
forn(i, start + 2, n - 1){
forn(j, i - start - 1, (i - start - 1) * 2){
dp[i][j] = max(dp[i - 1][j - 1], dp[i][j]);
dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j - 1] + (ll) attraction[i]);
tabla[j] = max(tabla[j], dp[i][j]);
tabla[j + 1] = max(tabla[j + 1], dp[i][j + 1]);
maximo = max(maximo, j + 1);
}
}
dp[start][1] = (ll) attraction[start];
res = max(res, tabla[max(min(maximo, d - 1), 0)]);
res = max(res, tabla[max(min(maximo, d - 2), 0)] + dp[start][1]);
far0(i, start){
forn(j, start - i, (start - i) * 2){
dp[i][j] = max(dp[i][j], dp[i + 1][j - 1]);
dp[i][j + 1] = max(dp[i][j + 1], dp[i + 1][j - 1] + (ll) attraction[i]);
if(j <= d){
res = max(res, dp[i][j]);
res = max(res, dp[i][j] + tabla[max(min(maximo, d - j - (start - i + 1)), 0)]);
}
if(j + 1 <= d){
res = max(res, dp[i][j + 1]);
res = max(res, dp[i][j + 1] + tabla[max(min(maximo, d - (j + 1) - (start - i + 1)), 0)]);
}
}
}
}
return res;
}
