#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
const int N = 100010;
int n, start, od, *att;
struct node {
int cnt;
ll sum;
node *l, *r;
node(int c, ll x) : cnt(c), sum(x), l(0), r(0) {}
node(node *l, node *r) : l(l), r(r), cnt(l->cnt+r->cnt), sum(l->sum+r->sum) {}
};
node *build(int b=0, int e=n-1) {
if (b == e) return new node(0, 0);
int m = (b+e)/2;
return new node(build(b, m), build(m+1, e));
}
node *update(int i, ll x, node *p, int b=0, int e=n-1) {
if (b == e) return new node(1, x);
int m = (b+e)/2;
if (i <= m) return new node(update(i, x, p->l, b, m), p->r);
else return new node(p->l, update(i, x, p->r, m+1, e));
}
ll query(int l, int r, node *p, int b=0, int e=n-1) {
if (b >= l && e <= r) return p->sum;
if (b > r || e < l) return 0;
int m = (b+e)/2;
return query(l, r, p->l, b, m) + query(l, r, p->r, m+1, e);
}
int bsearch(ll c, node *pl, node *pr, int b=0, int e=n-1) {
if (b == e) return b;
int m = (b+e)/2;
int lcnt = pr->l->cnt - pl->l->cnt;
if (lcnt >= c)
return bsearch(c, pl->l, pr->l, b, m);
else
return bsearch(c-lcnt, pl->r, pr->r, m+1, e);
}
bool inrev = false;
node *root[N];
int rev[N];
pli val[N];
inline ll topk(int l, int r, int k)
{
if (inrev) {
l = n-l-1;
r = n-r-1;
swap(l, r);
}
int i = bsearch(k, root[l], root[r+1]);
ll sum = query(0, i, root[r+1]) - query(0, i, root[l]);
return sum;
}
inline pli solve(int s, int al, int ar)
{
int d = od-(start-s);
pli ans(0, -1);
for (int i = max(s, al); i <= ar; ++i) {
int num = d-(i-s);
if (num <= 0) break;
ans = max(ans, pli(topk(s, i, num), i));
}
return ans;
}
ll dncopt(int b, int e, int al, int ar)
{
if (b > e) return 0;
int m = (b+e)/2;
pli ans = solve(m, al, ar);
ll q1 = dncopt(b, m-1, al, ans.second);
ll q2 = dncopt(m+1, e, ans.second, ar);
return max(ans.first, max(q1, q2));
}
ll routine()
{
return dncopt(0, start, 0, n-1);
}
ll findMaxAttraction(int n, int start, int d, int att[])
{
::n = n, ::start = start, ::od = d, ::att = att;
for (int i = 0; i < n; ++i)
val[i] = pli(att[i], i);
sort(val, val+n, greater<pli>());
for (int i = 0; i < n; ++i)
rev[val[i].second] = i;
root[0] = build();
for (int i = 0; i < n; ++i)
root[i+1] = update(rev[i], att[i], root[i]);
ll mxans = routine();
if (start > 0) {
inrev = true;
::start = n-start-1;
reverse(att, att+n);
mxans = max(mxans, routine());
}
return mxans;
}
/*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;
}*/
