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 <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <deque>

using namespace std;

template<typename T, typename S>
istream& operator >> (istream& is, pair<T, S>& p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& v) {
    for (auto& x : v) {
        is >> x;
    }
    return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& v) {
    for (auto& x : v) {
        os << x << " ";
    }
    os << "\n";
    return os;
}

struct MaxQueue {
    deque<int64_t> q;

    int64_t max() const {
        return q.front();
    }

    void push(int64_t x) {
        while (!q.empty() && q.back() < x)
            q.pop_back();
        q.push_back(x);
    }

    void pop(int64_t x) {
        if (!q.empty() && q.front() == x)
            q.pop_front();
    }
};

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int N, M, K;
    cin >> N >> M >> K;
    vector<int64_t> A(N);
    cin >> A;
    vector<vector<int64_t>> dp(K + 1, vector<int64_t>(N + 1, 0));
    for (int64_t k = 1; k <= K; ++k) {
        MaxQueue prev_M;
        if (k == 1) prev_M.push(0);
        for (int i = 0; i < N; ++i) {
            if (i >= k - 1) {
                dp[k][i + 1] = prev_M.max() + k * A[i];
            }
            prev_M.push(dp[k - 1][i + 1]);
            if (i >= M) prev_M.pop(dp[k - 1][i + 1 - M]);
        }
    }
    int64_t max_ans = dp[K][N];
    for (int i = 1; i < N; ++i) {
        if (dp[K][i] > max_ans) max_ans = dp[K][i];
    }
    cout << max_ans;
}