/*
Author: baodat
※\(^o^)/※
Current goal: Training for VNOI shirt
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long int
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define db double
#define ldb long double
#define all_1(x) (x).begin() + 1, (x).end()
#define all(x) (x).begin(), (x).end()
#define ins insert
#define pb push_back
template<typename T>void debug_var(const T& var, const string& name){
cerr << name << ": " << var << "\n";
}
template<typename T>void debug_1d(const T& vt, const string& name){
if(vt.empty()){
cerr << name << " is empty!\n";
return;
}
FOR(i, 0, (int)vt.size() - 1){
cerr << name << "[" << i << "]: " << vt[i] << "\n";
}
}
const ll oo = 2e18;
const int N = 1e5 + 5;
struct Data{
int cl, cr;
ll sum, cnt;
}st[24 * N];
int root[N];
int amount_node = 0;
vector<int> comp;
int get(int x){
return lower_bound(all(comp), x) - comp.begin() + 1;
}
int build(int l, int r){
int i = ++amount_node;
if(l == r){
return i;
}
int m = (l + r) >> 1;
st[i].cl = build(l, m);
st[i].cr = build(m + 1, r);
return i;
}
int update(int prv_ver, int l, int r, int pos, int val){
int i = ++amount_node;
st[i] = st[prv_ver];
++st[i].cnt;
st[i].sum += val;
if(l == r) return i;
int m = (l + r) >> 1;
if(pos <= m) st[i].cl = update(st[prv_ver].cl, l, m, pos, val);
else st[i].cr = update(st[prv_ver].cr, m + 1, r, pos, val);
return i;
}
ll query(int ver1, int ver2, int l, int r, int k){
if(l > r) return 0;
if(st[ver1].cnt - st[ver2].cnt <= k) return st[ver1].sum - st[ver2].sum;
if(l == r){
return 1ll * k * comp[l - 1];
}
int m = (l + r) >> 1;
int amount = st[st[ver1].cr].cnt - st[st[ver2].cr].cnt;
if(k <= amount) return query(st[ver1].cr, st[ver2].cr, m + 1, r, k);
return st[st[ver1].cr].sum - st[st[ver2].cr].sum + query(st[ver1].cl, st[ver2].cl, l, m, k - amount);
}
int n, start, d, attraction[N];
ll ans = 0;
void DaC(int R_L, int R_R, int L_L, int L_R){
if(R_L > R_R) return;
int mid_R = (R_L + R_R) >> 1;
ll maxi = -1, best_L = L_L;
FOR(i, L_L, min(L_R, min(mid_R, start))){
if(mid_R < start) continue;
//kth max element from [i..mid_r]
int k = d - ((start - i) + (mid_R - i));
ll res = -1;
if(k > 0)res = query(root[mid_R], root[i - 1], 1, n, k);
if(res > maxi){
maxi = res;
best_L = i;
}
}
ans = max(ans, maxi);
DaC(R_L, mid_R - 1, L_L, best_L);
DaC(mid_R + 1, R_R, best_L, L_R);
}
ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]){
n = _n;
start = _start + 1;
d = _d;
FOR(i, 1, n) attraction[i] = _attraction[i - 1];
FOR(i, 1, n) comp.pb(attraction[i]);
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
//right -> left
amount_node = 0;
root[0] = build(1, n);
FOR(i, 1, n) root[i] = update(root[i - 1], 1, n, get(attraction[i]), attraction[i]);
DaC(start, n, 1, n);
reverse(attraction + 1, attraction + 1 + n);
//now it's left -> right
amount_node = 0;
start = n - start + 1;
FOR(i, 0, n) root[i] = 0;
FOR(i, 0, 24 * N - 1) st[i].cl = st[i].cr = st[i].sum = st[i].cnt = 0;
root[0] = build(1, n);
FOR(i, 1, n) root[i] = update(root[i - 1], 1, n, get(attraction[i]), attraction[i]);
DaC(start, n, 1, n);
return ans;
}
void solve(){
int d = 7;
int n = 5;
int start = 2;
int a[5] = {10, 2, 20, 30, 1};
cout << findMaxAttraction(n, start, d, a) << "\n";
}
/*
go Right -> Left
then reverse
the answer is max(Right -> Left, reverse the a then Right -> left again)
if we continue to move right
l must stay or move right too
*/
