#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
const int SZ=1<<20;
char gchar()
{
static char buf[SZ];
static int i=SZ;
if(i==SZ)i=0,fread(buf,1,SZ,stdin);
return buf[i++];
}
void pchar(char c)
{
static char buf[SZ];
static int i=0;
if(c)buf[i++]=c;
if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
}
void pstr(string s,char end='\n')
{
for(char c:s)pchar(c);
pchar(end);
}
template<typename T>void read(T &x)
{
x=0;int f=1;
static char c;
while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
x=c-'0';
while((c=gchar())>='0'&&c<='9')
x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template<typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template<typename T>void i_write(T x)
{
if(x>9)i_write(x/10);
pchar(x%10+'0');
}
template<typename T>void write(T x,char end='\n')
{
if(x<0)pchar('-'),x=-x;
if(x>9)i_write(x/10);
pchar(x%10+'0');
pchar(end);
}
}
using IO::read;
using IO::write;
const int N=1e5+10;
int n,s,d,rt[N],cnt;
ll a[N],b[N];
struct SegmentTree
{
int ls[N<<5],rs[N<<5],c[N<<5],idx;
ll s[N<<5];
void pushup(int p){s[p]=s[ls[p]]+s[rs[p]],c[p]=c[ls[p]]+c[rs[p]];}
void upd(int &p,int q,int l,int r,int x)
{
p=++idx,ls[p]=ls[q],rs[p]=rs[q],c[p]=c[q],s[p]=s[q];
if(l==r)return c[p]++,s[p]+=b[x],void();
int mid=(l+r)>>1;
if(x<=mid)upd(ls[p],ls[q],l,mid,x);
else upd(rs[p],rs[q],mid+1,r,x);
pushup(p);
}
ll ask(int p,int q,int l,int r,int k)
{
if(k<=0)return 0;
if(c[p]-c[q]<k)return s[p]-s[q];
if(l==r)return b[l]*k;
int mid=(l+r)>>1;
if(k<=c[rs[p]]-c[rs[q]])return ask(rs[p],rs[q],mid+1,r,k);
return ask(ls[p],ls[q],l,mid,k-(c[rs[p]]-c[rs[q]]))+s[rs[p]]-s[rs[q]];
}
}sgt;
ll calc(int l,int r){return sgt.ask(rt[r],rt[l-1],1,cnt,d-(2*(r-s)+s-l));}
ll ans;
void solve(int l,int r,int L,int R)
{
if(l>r)return;
if(L==R)
{
for(int i=l;i<=r;i++)ans=max(ans,calc(i,L));
return;
}
int pos=L,mid=(l+r)>>1;ll mx=calc(mid,L);
for(int i=L+1;i<=R;i++)
{
ll v=calc(mid,i);
if(v>mx)mx=v,pos=i;
}
ans=max(ans,mx),solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
}
void work()
{
for(int i=1;i<=n;i++)rt[i]=0;
for(int i=1;i<=sgt.idx;i++)sgt.ls[i]=sgt.rs[i]=sgt.c[i]=sgt.s[i]=0;
sgt.idx=0;
for(int i=1;i<=n;i++)sgt.upd(rt[i],rt[i-1],1,cnt,a[i]);
for(int i=1;i<=s;i++)ans=max(ans,calc(i,s));
solve(1,s-1,s+1,n);
}
ll findMaxAttraction(int _n,int _s,int _d,int _a[])
{
n=_n,s=_s+1,d=_d;
for(int i=1;i<=n;i++)a[i]=_a[i-1],b[i]=a[i];
sort(b+1,b+n+1),cnt=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
work();
s=n-s+1,reverse(a+1,a+n+1);
work();
return ans;
}
