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;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

template<class T, class F>
struct slidingWindowAggregation {
    // using F = function<T(T,T)>;
    F f;
    T d;
    stack<pair<T,T>> st1, st2;
    slidingWindowAggregation(F f, T d) : f(f), d(d) {}
    T fold_all() { 
        if(st1.size() && st2.size()) return f(st1.top().second, st2.top().second); 
        if(st2.size()) return st2.top().second;
        if(st1.size()) return st1.top().second;
        return d;
    }
    void push(T x) { 
        const T rui = st2.size() ? f(st2.top().second, x) : x;
        st2.push({x, rui}); 
    }
    void pop() {
        if(st1.empty()) {
            T rui = d;
            while(st2.size()) {
                T t; tie(t, ignore) = st2.top(); st2.pop();
                rui = f(rui, t);
                st1.push({t, rui});
            }
        }
        st1.pop();
    }
};

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

    // dp[i回投げた][最後に当てたのがj]
    // dp[i][j] = max(dp[i-1][k]) + (i+1)*j j-m<=k<=j-1
    vector<vector<ll>> dp(k, vector<ll>(n, -INF));
    REP(i, n) dp[0][i] = a[i]; 
    FOR(i, 1, k) {
        auto f = [&](ll l, ll r) { return max(l, r); };
        slidingWindowAggregation<ll, decltype(f)> swag(f, -INF);
        REP(j, n) {
            dp[i][j] = swag.fold_all() + (i+1)*a[j];
            swag.push(dp[i-1][j]);
            if(j >= m) swag.pop();
        }
        dump(i, dp[i]);
    }

    ll ret = 0;
    REP(i, n) chmax(ret, dp[k-1][i]);
    cout << ret << endl;

    return 0;
}