Problem: There are N panels arranged in a row in Takahashi's house, numbered 1 through N. The i-th panel has a number A_i written on it. Takahashi is playing by throwing balls at these panels.

Takahashi threw a ball K times. Let the panel hit by a boll in the i-th throw be panel p_i. He set the score for the i-th throw as i \times A_{p_i}.

He was about to calculate the total score for his throws, when he realized that he forgot the panels hit by balls, p_1,p_2,...,p_K. The only fact he remembers is that for every i (1 ≦ i ≦ K-1), 1 ≦ p_{i+1}-p_i ≦ M holds. Based on this fact, find the maximum possible total score for his throws.

Constraints

* 1 ≦ M ≦ N ≦ 100,000
* 1 ≦ K ≦ min(300,N)
* 1 ≦ A_i ≦ 10^{9}

Input

The input is given from Standard Input in the following format:


N M K
A_1 A_2 … A_N


Output

Print the maximum possible total score for Takahashi's throws.

Examples

Input

5 2 3
10 2 8 10 2


Output

56


Input

5 5 2
5 2 10 5 9


Output

28


Input

10 3 5
3 7 2 6 9 4 8 5 1 1000000000


Output

5000000078

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////

int main(){fastio
    ll n,m,k;cin>>n>>m>>k;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll dp[n][k];memset(dp,0,sizeof(dp));
    rep(i,0,n-1){
        dp[i][0]=a[i];
    }
    //rep(i,0,n-1)cout<<dp[i][0]<<" ";cout<<endl;
    rep(j,1,k-1){
        deque<ll>dq;
        rep(i,0,n-1){
            while(dq.size()!=0&&dp[dq.back()][j-1]<dp[i][j-1]){
                dq.pop_back();
            }
            if(i>=j)dp[i][j]=dp[dq.front()][j-1]+a[i]*(j+1);
            dq.push_back(i);
            if(dq.front()==i-m){
                dq.pop_front();
            }
            //cout<<dp[i][j]<<" ";
            //cout<<dq.size()<<" ";
        }//cout<<endl;
    }/*
    rep(j,0,k-1){
        rep(i,0,n-1){
            cout<<dp[i][j]<<" ";
        }cout<<endl;
      }*/
    
    ll ans=0;
    rep(j,0,n-1)Max(ans,dp[j][k-1]);
    cout<<ans<<endl;
    
    return 0;
}
/*
 5 2 3
 10 3 8 9 2
 */