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>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
int M,N,K;
ll A[100000];
ll dp[100000][300];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>M>>K;
    rep(i,0,N) cin>>A[i];
    rep(i,0,N) dp[i][1]=A[i];
    rep(j,2,K+1){
        deque<ll> d;
        ll m=0;
        rep(i,j-1,N){
            while(sz(d)&&dp[d.back()][j-1]<=dp[i-1][j-1]){
                d.pop_back();
            }
            d.push_back(i-1);
            if(i-M+1>=j-1){
                dp[i][j]=dp[d.front()][j-1]+A[i]*j;
                if(d.front()==i-M) d.pop_front();
            }
            else{
                m=max(m,dp[i-1][j-1]);
                dp[i][j]=m+A[i]*j;
            }
        }
    }
    ll M=0;
    rep(i,K-1,N) M=max(M, dp[i][K]);
    cout <<M<<"\n";
}