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 llong long long int
#define ldouble long double
#define rep(i, n) for (int i = 0; i < n; ++i)
#define fore(i,a) for (auto &i : a)
#define repr(i, n) for (int i = n; i >= 0; --i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

const static int mod = 1000000000 + 7;
const static int inf = INT_MAX / 2;
const static llong INF = LLONG_MAX / 2;
const static double eps = 1e-10;
const static int dx[] = {1, 0, -1, 0};
const static int dy[] = {0, 1, 0, -1};

template<typename T> vector<T> slide_max(const vector<T> &V, int width) {
    deque<T> deq;
    vector<T> ret;

    for(int i = 0; i < V.size(); i++) {
        while(!deq.empty() && V[deq.back()] <= V[i]) {
            deq.pop_back();
        }

        deq.push_back(i);
        ret.emplace_back(deq.front());

        if(i - width + 1 >= 0) {
            if(deq.front() == i - width + 1) deq.pop_front();
        }
    }
    
    return ret;
}

signed main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M, K;
    cin >> N >> M >> K;
    vector<llong> A(N);
    rep(i, N) cin >> A[i];

    vector<llong> pre_dp(N);
    rep(i, N) pre_dp[i] = A[i];

    for (int k = 2; k <= K; ++k) {
        vector<llong> next_dp(N, 0);

        vector<llong> smax = slide_max<llong>(pre_dp, M);

        for (int i = k - 1; i < N; ++i) {
            next_dp[i] = max(next_dp[i], pre_dp[smax[i - 1]] + k * A[i]);
        }

        pre_dp.swap(next_dp);
    }

    llong ans = -1;
    rep(i, pre_dp.size()) {
        ans = max(ans, pre_dp[i]);
    }

    cout << ans << endl;

    return 0;
}