1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #define rep(i,l,r) for (int i=l; i<=r; i++)
5 typedef long long ll;
6 using namespace std;
7
8 const int N=250010,M=1800010;
9 int n,st,m,cnt,root[N],b[N],sta[N],c,ls[M],rs[M],sz[M];
10 ll ret,ans,sum[M],f[N],g[N],f1[N],g1[N];
11 int fd[N],gd[N],f1d[N],g1d[N];
12
13 void ins(int x,int &y,int l,int r,int val,ll Val){
14 sz[y=++cnt]=sz[x]+1; sum[y]=sum[x]+Val; ls[y]=ls[x];rs[y]=rs[x];
15 if (l==r) return; int mid=(l+r)>>1;
16 if (val<=mid) ins(ls[x],ls[y],l,mid,val,Val);
17 else ins(rs[x],rs[y],mid+1,r,val,Val);
18 }
19
20 void query(int x,int y,int l,int r,int k){
21 if (k<=0) return;
22 if (l==r) { ret+=1ll*min(k,sz[y]-sz[x])*sta[l]; return; }
23 int mid=(l+r)>>1;
24 if (sz[rs[y]]-sz[rs[x]]>=k) query(rs[x],rs[y],mid+1,r,k);
25 else ret+=sum[rs[y]]-sum[rs[x]],query(ls[x],ls[y],l,mid,k-sz[rs[y]]+sz[rs[x]]);
26 }
27
28 void solve1(int l,int r,int L,int R){//要求f[l..r],d的范围在[L,R]
29 if (l>r) return;
30 int mid=(l+r)>>1;
31 for (int i=L;i<=R;i++){
32 ret=0; query(root[st-1],root[i],1,c,st-i+mid);
33 if (ret>f[mid]||!fd[mid]) f[mid]=ret,fd[mid]=i;
34 }
35 solve1(l,mid-1,L,fd[mid]);solve1(mid+1,r,fd[mid],R);
36 }
37
38 void solve2(int l,int r,int L,int R){
39 if (l>r) return;
40 int mid=(l+r)>>1;
41 for (int i=R; i>=L; i--){
42 ret=0; query(root[i-1],root[st-1],1,c,i-st+mid);
43 if (ret>g[mid]||!gd[mid]) g[mid]=ret,gd[mid]=i;
44 }
45 solve2(l,mid-1,gd[mid],R); solve2(mid+1,r,L,gd[mid]);
46 }
47
48 void solve3(int l,int r,int L,int R){
49 if (l>r) return;
50 int mid=(l+r)>>1;
51 for (int i=L; i<=R; i++){
52 ret=0; query(root[st-1],root[i],1,c,((st-i)<<1)+mid);
53 if (ret>f1[mid]||!f1d[mid]) f1[mid]=ret,f1d[mid]=i;
54 }
55 solve3(l,mid-1,L,f1d[mid]); solve3(mid+1,r,f1d[mid],R);
56 }
57
58 void solve4(int l,int r,int L,int R){
59 if (l>r) return;
60 int mid=(l+r)>>1;
61 for (int i=R;i>=L;i--){
62 ret=0; query(root[i-1],root[st-1],1,c,((i-st)<<1)+mid);
63 if (ret>g1[mid]||!g1d[mid]) g1[mid]=ret,g1d[mid]=i;
64 }
65 solve4(l,mid-1,g1d[mid],R);solve4(mid+1,r,L,g1d[mid]);
66 }
67
68 int main(){
69 freopen("bzoj4367.in","r",stdin);
70 freopen("bzoj4367.out","w",stdout);
71 scanf("%d%d%d",&n,&st,&m);st++;
72 rep(i,1,n) scanf("%d",&b[i]),sta[i]=b[i];
73 sort(sta+1,sta+n+1);c=unique(sta+1,sta+n+1)-sta-1;
74 rep(i,1,n) b[i]=lower_bound(sta+1,sta+c+1,b[i])-sta;
75 rep(i,1,n) ins(root[i-1],root[i],1,c,b[i],sta[b[i]]);
76 solve1(1,m,st,min(n,st+m)); solve2(1,m,max(1,st-m),n);
77 solve3(1,m,st,min(n,st+(m>>1))); solve4(1,m,max(1,st-(m>>1)),n);
78 rep(i,0,m) ans=max(ans,g1[i]+f[m-i]);
79 rep(i,0,m) ans=max(ans,f1[i]+g[m-i]);
80 printf("%lld\n",ans);
81 }