//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < k; i++)
#define pb push_back
#define X first
#define Y second
#define for_all(x) x.begin(), x.end()
constexpr int N = 1e5 + 10;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
inline void smax(ll& l, ll r) { l = l > r ? l : r; }
struct ziba {
int s, t, l, r;
ziba() {}
ziba(int s, int t, int l, int r) : s(s), t(t), l(l), r(r) {}
};
int n, s, d, a[N], n2;
ll dp[4][N * 3];
vector<int> A;
inline int Locate(int v) { return lower_bound(for_all(A), v) - A.begin(); }
int active[N * 4];
ll seg[4 * N];
void segAct(int pos, int l = 0, int r = n2, int id = 1) {
if (l == r - 1) {
active[id]++;
seg[id] += A[l];
return;
}
int mid = l + r >> 1;
if (pos < mid)
segAct(pos, l, mid, id << 1);
else
segAct(pos, mid, r, id << 1 | 1);
active[id] = active[id << 1] + active[id << 1 | 1];
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
ll segGet(int& rem, int l = 0, int r = n2, int id = 1) {
if (rem >= active[id]) {
rem -= active[id];
return seg[id];
}
if (l == r - 1) {
int go = min(rem, active[id]);
rem -= go;
return go * A[l];
}
int mid = l + r >> 1;
ll res = segGet(rem, mid, r, id << 1 | 1);
if (rem) res += segGet(rem, l, mid, id << 1);
return res;
}
ziba Q[N * 4];
int L, R;
inline void solve(int to, int c, int l, int r) {
memset(seg, 0, sizeof(seg));
memset(active, 0, sizeof(active));
L = R = 0;
Q[R++] = ziba(l + 1, r, 1, (r - l + 1) * (1 + c));
int added = l;
while (L != R) {
ziba now = Q[L++];
int mid = now.l + now.r >> 1;
if (now.s < added) {
added = l;
memset(seg, 0, sizeof(seg));
memset(active, 0, sizeof(active));
}
int pos = now.t;
rep(i, now.s, now.t + 1) {
while (added < i) {
added++;
segAct(Locate(a[added]));
}
int rem = mid - (i - l) * c;
if (rem <= 0) continue;
ll happy = segGet(rem);
if (happy > dp[to][mid]) {
dp[to][mid] = happy;
pos = i;
}
}
if (mid - 1 >= now.l) Q[R++] = ziba(now.s, pos, now.l, mid - 1);
if (mid + 1 <= now.r) Q[R++] = ziba(pos, now.t, mid + 1, now.r);
}
}
/*
5 0 6
10 2 20 30 1
*/
long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
n = n_;
s = start_;
d = d_;
s++;
rep(i, 1, n + 1) {
a[i] = attraction[i - 1];
A.push_back(a[i]);
}
sort(for_all(A));
A.resize(unique(for_all(A)) - A.begin());
n2 = A.size();
solve(0, 1, s, n);
solve(1, 2, s, n);
reverse(a + 1, a + s + 1);
solve(2, 1, 1, s);
solve(3, 2, 1, s);
ll best = 0;
rep(i, 1, 3 * n + 1) rep(j, 0, 4) smax(dp[j][i], dp[j][i - 1]);
rep(i, 0, d + 1) {
smax(best, dp[0][i] + dp[3][d - i]);
smax(best, dp[1][i] + dp[2][d - i]);
if (i) {
smax(best, dp[0][i - 1] + dp[3][d - i] + a[1]);
smax(best, dp[1][i - 1] + dp[2][d - i] + a[1]);
}
}
return best;
}
