#include <bits/stdc++.h>
using namespace std;
#include"holiday.h"
// struct KSum {
// int k = 0, ptr = 0;
// multiset<int> mx;
// multiset<int> mn;
// ll sum = 0;
//
// void inc () {
// assert(mn.size());
// auto ptr = prev(mn.end());
// mx.insert(*ptr);
// sum += *ptr;
// mn.erase(ptr);
// k++;
// }
//
// void dec () {
// assert(mx.size());
// auto ptr = mx.begin();
// mn.insert(*ptr);
// sum -= *ptr;
// mx.erase(ptr);
// k--;
// }
//
// void add (int val) {
// mn.insert(val);
// if (mx.size()) {
// dec();
// inc();
// }
// }
// };
// ll solve (int n, int s, int d, vector<int> a) {
// if (d == 0) return 0;
// vector<int> sg;
//
// sg.eb(0);
// for (int i=s+1; i<n; i++) {
// sg.eb(a[i]);
// }
// for (int i=0; i<d+13; i++) {
// sg.eb(0);
// }
//
// vector<ll> msg(d+1, 0);
// KSum l, r;
// l.add(sg[1]);
// r.add(sg[1]);
// r.add(sg[2]);
// int bst = 1;
// for (int i=2; i<=d; i++) {
// while (l.k < bst && l.k+bst < i) {
// l.inc();
// }
// while (r.k < bst+1 && r.k+bst+1 < i) {
// r.inc();
// }
// while (bst + 2 <= SZ(sg) && r.sum >= l.sum) {
// l.add(sg[++bst]);
// r.add(sg[bst+1]);
// if (l.k) {
// l.dec();
// }
// if (r.k) {
// r.dec();
// }
// debug(bst, l.sum, r.sum);
// while (l.k < bst && l.k+bst < i) {
// l.inc();
// }
// while (r.k < bst+1 && r.k+bst+1 < i) {
// r.inc();
// }
// }
// debug(l.k, bst);
// msg[i] = l.sum;
// }
// debug(sg, msg);
// return max(a[s] + msg[d-1], msg[d]);
// }
//long long int full (int n, int start, int d, int attraction[]) {
//vector<int> a;
//for (int i=0; i<n; i++) {
//a.eb(attraction[i]);
//}
//ll la = solve(n, start, d, a);
//reverse(ALL(a));
//ll ra = solve(n, n-1-start, d, a);
//return max(la, ra);
//}
typedef long long ll;
long long int findMaxAttraction (int n, int start, int d, int a[]) {
assert(start == 0);
ll ans = 0;
for (int _i=1002; _i>=0; _i--) {
int cnt = 0;
ll cur = 0;
for (int i=0; i<n; i++) {
if (a[i] >= _i) {
cnt++;
cur += a[i];
}
if (cnt + i > d) break;
ans = max(ans, cur);
}
}
//assert(ans == full(n, start, d, a));
return ans;
}
