#ifndef mikevui
#include "holiday.h"
#endif // mikevui
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
#define ALL(v) (v).begin(), (v).end()
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 1e5+5;
int n, d;
vector<int> a, b;
ll dp1[maxn*3][2], dp2[maxn*3][2]; //left, right | 1 -> ret
multiset<int> st1, st2; //chosen, waiting
ll cursum = 0, ans = 0;
//ll debugsum = 0;
void dnc(int l, int r, int opl, int opr, bool ret, vector<int> &a, ll dp[][2]) {///assume 1 -> opl-1
// cout << l << ' ' << r << ' ' << opl << ' ' << opr << ' ' << ret << endl;
// system("pause");
// debugsum += opr-opl+1;
int mid = (l+r)>>1; ///d = mid
int opt = -1; ///case -1 when cannot move anywhere
ll best = -1;
for (int i = opl; i <= opr; i++) {
//inc dis -> remove 1/2 element(s)
int numele = mid-i*(1+ret);
st2.insert(a[i]);
// if (numele < 0) break;
//move 1 -> 2
while ((int)st1.size() > numele && !st1.empty()) {
int val = (*st1.begin());
st1.erase(st1.begin());
cursum -= val;
st2.insert(val);
}
while ((int)st1.size() < numele && !st2.empty()){
auto it = prev(st2.end());
int val = (*it);
st2.erase(it);
cursum += val;
st1.insert(val);
}
while ((!st1.empty() && !st2.empty()) && (*st1.begin()) < (*st2.rbegin())) {
auto it = prev(st2.end());
int val1 = (*st1.begin()), val2 = (*it);
st1.erase(st1.begin());
st2.erase(it);
st1.insert(val2);
st2.insert(val1);
cursum += val2-val1;
}
if (maximize(best, cursum)) {
opt = i;
}
}
// cout << "case " << l << ' ' << r << ' ' << mid << ' ' << opl << ' ' << opr << ' ' << ret << "\n";
// cout << "opt here " << opt << endl;
// for (auto it : st1) {
// cout << it << ' ';
// }
// cout << endl;
// for (auto it : st2) {
// cout << it << ' ';
// }
// cout << endl;
dp[mid][ret] = best;
for (int i = opt; i <= opr; i++) {
// cout << i << endl;
int val = a[i];
auto it = st2.find(val);
if (it == st2.end()) {
// assert(st1.find(val) != st1.end());
st1.erase(st1.find(val));
cursum -= val;
}
else {
st2.erase(it);
}
// cout << "ok" << endl;
}
// cout << "ok phase 1" << endl;
if (mid != r) {
dnc(mid+1, r, opt, opr, ret, a, dp);
}
for (int i = opl; i < opt; i++) {
int val = a[i];
auto it = st2.find(val);
if (it == st2.end()) {
st1.erase(st1.find(val));
cursum -= val;
}
else {
st2.erase(it);
}
}
// cout << "ok phase 2" << endl;
if (mid != l) {
dnc(l, mid-1, opl, opt, ret, a, dp);
}
}
ll findMaxAttraction(int N, int S, int D, int A[]) {
for (int i = S; i >= 0; i--) {
a.pb(A[i]);
}
for (int i = S; i < N; i++) {
b.pb(A[i]);
}
d = D;
//dnc
memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
if ((int)a.size() > 1) {
dnc(1, d, 1, (int)a.size()-1, 0, a, dp1);
cursum = 0;
st1.clear();
st2.clear();
if ((int)a.size() > 2) {
dnc(2, d, 1, (int)a.size()-1, 1, a, dp1);
cursum = 0;
st1.clear();
st2.clear();
}
}
// cout << "HERE COME THE 2ND" << endl;
if ((int)b.size() > 1) {
dnc(1, d, 1, (int)b.size()-1, 0, b, dp2);
cursum = 0;
st1.clear();
st2.clear();
if ((int)b.size() > 2) {
dnc(2, d, 1, (int)b.size()-1, 1, b, dp2);
}
}
// cout << debugsum << "\n";
// for (int i= 1; i <= d; i++) {
// cout << dp1[i][0] << ' ';
// }
// cout << "\n";
// for (int i= 1; i <= d; i++) {
// cout << dp1[i][1] << ' ';
// }
// cout << "\n";
// for (int i= 1; i <= d; i++) {
// cout << dp2[i][0] << ' ';
// }
// cout << "\n";
// for (int i= 1; i <= d; i++) {
// cout << dp2[i][1] << ' ';
// }
// cout << "\n";
//for each d1, d2 -> cal with/without st
for (int d1 = 0; d1 <= d; d1++) {
int d2 = d-d1;
//case left right
maximize(ans, dp1[d1][1]+dp2[d2][0]);
//case right left
maximize(ans, dp1[d1][0]+dp2[d2][1]);
//consider start
if (d1 < d) {
d2 = d-d1-1;
maximize(ans, dp1[d1][1]+dp2[d2][0]+a[0]);
maximize(ans, dp1[d1][0]+dp2[d2][1]+a[0]);
}
}
return ans;
}
#ifdef mikevui
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
int N, S, D, A[maxn];
cin >> N >> S >> D;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
cout << findMaxAttraction(N, S, D, A);
}
#endif // mikevui
/**
5 2 7
8 10 1 1 21
7 4 16
1 4 3 9 2 4 9
10 1 20
32 13 82 81 93 22 10 43 21 98
20 18 40
32 13 82 81 93 22 10 43 21 98 43 12 43 82 95 32 18 90 43 12
*/
