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;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

//O(NKlogN)が通らないの険しすぎる
//スライド最小値
//配列vの幅kごとの最小値を返す。返す配列のサイズはv.size()-k+1になる
//pop_back,push_back,pop_frontそれぞれN回しかないからO(N)
template<typename T>
vector<T> slide_min(const vector<T> &v,int k){
    //idxとvalueが昇順になるようにdequeに入れる
    deque<int> dq;
    vector<T> ret;
    for(int i=0;i<v.size();i++){
        //不等号: <=ならslide max  >=ならslide minになる
        while(!dq.empty()&&v[dq.back()]<=v[i]){
            dq.pop_back();
        }
        dq.push_back(i);
        if(i-k+1>=0){
            ret.push_back(v[dq.front()]);
            if(dq.front()==i-k+1) dq.pop_front();
        }
    }
    return ret;
}
/////


int main(){
    ll n,m,k;
    cin>>n>>m>>k;
    vector<ll> a(n);
    rep(i,n){
        cin>>a[i];
    }

    vector<ll> dp(n,0);
    //一つ目
    rep(i,n) dp[i]=a[i];
    for(int times=2;times<=k;times++){
        vector<ll> dpp(n,0);

        //slide max
        //前半の範囲がm個ないところは0補充しておけばok
        reverse(ALL(dp));
        for(int mugen=0;mugen<m-1;mugen++) dp.push_back(0ll);
        reverse(ALL(dp));
        auto sm=slide_min(dp,m);
        for(int j=times-1;j<n;j++){
            dpp[j]=sm[j-1]+times*a[j];
        }


        swap(dp,dpp);
    }
    ll ans=0;
    rep(i,dp.size()) ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}