#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
//vector<int> values;
vector<vector<long long int>> dp;
int N, D, START;
long long solveLeft(int city, int day, int attraction[]){
if(city < 0) return 0;
if(day <= 0) return 0;
if(dp[city][day] != -1) return dp[city][day];
dp[city][day] = max(solveLeft(city-1, day-1, attraction), solveLeft(city-1, day-2, attraction) + (long long)attraction[city]);
return dp[city][day];
}
long long solveRight(int city, int day, int attraction[]){
if(city >= N) return 0;
if(day <= 0) return 0;
if (dp[city][day] != -1) return dp[city][day];
//cout << city << " " << day << " " << dp[city][day] << endl;
dp[city][day] = max((long long)attraction[city] + solveLeft(START-1, day - (city - START + 1) - 1, attraction),
max((long long)attraction[city] + solveRight(city+1, day-2, attraction),
max(solveRight(city+1, day-1, attraction),
solveLeft(START-1, day - (city - START + 1), attraction))));
return dp[city][day];
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
dp = vector<vector<long long int>>(n, vector<long long int>(d+1, -1));
N = n; D = d; START = start;
/*
for(int i = 0; i < n; ++i) values[i] = attraction[i];
*/
return solveRight(start, d, attraction);
}
/*
int main(){
int n, d, start;
cin >> n >> start >> d;
int cities[n];
for(int i = 0; i < n; ++i) cin >> cities[i];
cout<< findMaxAttraction(n, start, d, cities) << endl;
return 0;
}*/
