#include using namespace std; using ll = long long; template inline bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; } struct LazySegmentTree{ private: int n; vector node, lazy; public: LazySegmentTree(vector v){ int sz= v.size(); n=1; while(n=0; i--) node[i]=max(node[2*i+1],node[2*i+2]); } void eval(ll k,ll l,ll r){ if(lazy[k]!=0){ node[k]+=lazy[k]; if(r-l>1){ lazy[2*k+1]+=lazy[k]; lazy[2*k+2]+=lazy[k]; } lazy[k]=0; } } void add(ll a,ll b,ll x,ll k=0,ll l=0,ll r=-1){ if(r<0) r=n; eval(k,l,r); if(b<=l || r<=a) return; if(a<=l && r<=b){ lazy[k]+=x; eval(k,l,r); } else{ add(a,b,x,2*k+1,l,(l+r)/2); add(a,b,x,2*k+2,(l+r)/2,r); node[k]=max(node[2*k+1],node[2*k+2]); } } ll getmax(ll a,ll b,ll k=0,ll l=0,ll r=-1){ if(r<0) r=n; if(b<=l || r<=a) return 0; eval(k,l,r); if(a<=l && r<=b) return node[k]; ll vl=getmax(a,b,2*k+1,l,(l+r)/2); ll vr=getmax(a,b,2*k+2,(l+r)/2,r); return max(vl,vr); } }; void main_() { int n,b,c; cin >> n >> b >> c; vector a(n); for(int i = 0; i < n; i++)cin >> a[i]; vector> dp(2,vector(n+1)); ll ans = 0; LazySegmentTree one(dp[0]), two(dp[1]); if(b == 2){ for(int i = 0; i < n; i++){ ll zero_tmp, one_tmp; zero_tmp = one.getmax(max(0LL,(ll)i+2-c),i+1) + a[i]; if(i)one_tmp = one.getmax(max(0LL,(ll)i+1-c),i); one.add(i+1,i+2,one_tmp); if(i == n-1)ans = max(zero_tmp, one_tmp); one.add(0,i+1,a[i]); } } else { for(int i = 0; i < n; i++){ ll zero_tmp, one_tmp, two_tmp; zero_tmp = max(one.getmax(max(0LL,(ll)i+2-c),i+1), two.getmax(max(0LL,(ll)i+2-c),i+1)) + a[i]; if(i)one_tmp = max(one.getmax(max(0LL,(ll)i+1-c),i), two.getmax(max(0LL,(ll)i+1-c),i)); if(i)two_tmp = one.getmax(i,i+1); one.add(i+1,i+2,one_tmp); two.add(i+1,i+2,two_tmp); if(i == n-1)ans = max({zero_tmp, one_tmp, two_tmp}); one.add(0,i+1,a[i]); two.add(0,i+1,a[i]); } } cout << ans << endl; }; int main() { int t = 1; // cin >> t; while(t--) main_(); return 0; }