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 i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;

template <class Compare> class rmq {
    using value_compare = Compare;
    static constexpr ::std::size_t BLOCKSIZE = 16;
    using block_type = ::std::uint_least16_t;
    static_assert(BLOCKSIZE <= ::std::numeric_limits<block_type>::digits, "");
    using size_type = ::std::size_t;

private:
    static size_type msb(size_type c) {
#ifdef __has_builtin
        return 31 - __builtin_clz(c);
#else
        ::std::size_t ret = 0;
        if (c >> 8)
            c >>= 8, ret += 8;
        if (c >> 4)
            c >>= 4, ret += 4;
        if (c >> 2)
            c >>= 2, ret += 2;
        return ret + (c >> 1);
#endif
    }
    static size_type ctz(const block_type c) {
#ifdef __has_builtin
        return __builtin_ctz(c);
#else
        static const ::std::array<size_type, 16> table = {
            0, 1, 2, 5, 3, 9, 6, 11, 15, 4, 8, 10, 14, 7, 13, 12 };
        return table[(c & ~c + 1) * 0x9AFU >> 12 & 0xF];
#endif
    }

    value_compare comp;
    ::std::vector<block_type> small;
    ::std::vector<::std::vector<size_type>> large;

    size_type get_min(const size_type left, const size_type right) const {
        return comp(left, right) ? left : right;
    }

public:
    rmq() : comp(), small(), large() {}
    explicit rmq(const size_type size, const value_compare &x)
        : comp(x), small(), large() {
        ::std::vector<size_type> st;
        st.reserve(BLOCKSIZE);
        large.emplace_back();
        large.front().reserve(size / BLOCKSIZE);
        small.reserve(size);
        for (size_type i = 0; i < size; ++i) {
            while (!st.empty() && !comp(st.back(), i))
                st.pop_back();
            small.emplace_back(st.empty() ? 0 : small[st.back()]);
            small.back() |= static_cast<block_type>(1) << (i % BLOCKSIZE);
            st.emplace_back(i);
            if (!((i + 1) % BLOCKSIZE)) {
                large.front().emplace_back(st.front());
                st.clear();
            }
        }
        for (size_type i = 1; i << 1 <= size / BLOCKSIZE; i <<= 1) {
            ::std::vector<size_type> v;
            const size_type csz = size / BLOCKSIZE + 1 - (i << 1);
            v.reserve(csz);
            for (size_type k = 0; k < csz; ++k)
                v.emplace_back(get_min(large.back()[k], large.back()[k + i]));
            large.emplace_back(::std::move(v));
        }
    }

    size_type size() const { return small.size(); }

    size_type fold_closed(const size_type first, const size_type last) const {
        assert(first <= last);
        assert(last < size());

        const size_type left = first / BLOCKSIZE + 1;
        const size_type right = last / BLOCKSIZE;
        if (left < right) {
            const size_type p = msb(right - left);
            return get_min(
                get_min((left - 1) * BLOCKSIZE +
                    ctz(small[left * BLOCKSIZE - 1] &
                        ~static_cast<block_type>(0) << first % BLOCKSIZE),
                    large[p][left]),
                get_min(large[p][right - (static_cast<size_type>(1) << p)],
                    right * BLOCKSIZE + ctz(small[last])));
        }
        else if (left == right) {
            return get_min((left - 1) * BLOCKSIZE +
                ctz(small[left * BLOCKSIZE - 1] &
                    ~static_cast<block_type>(0) << first % BLOCKSIZE),
                left * BLOCKSIZE + ctz(small[last]));
        }
        else {
            return right * BLOCKSIZE + ctz(small[last] & ~static_cast<block_type>(0)
                << first % BLOCKSIZE);
        }
    }
};

template <class Compare>
rmq<Compare> make_rmq(const ::std::size_t size, const Compare &x) {
    return rmq<Compare>(size, x);
}

#include<cstdio>
#include<vector>
using uint = unsigned int;

void scan(uint &d) {
    d = 0;
    int c;
    while (c = fgetc(stdin), c == ' ' || c == '\n');
    do d = d * 10 + c - '0';
    while (c = fgetc(stdin), c != ' '&&c != '\n');
}

signed main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<i64> a(n);
    for(auto& x : a)
        cin >> x;

    auto b = a;


    for(int i = 1; i < k; ++i){
        auto seg = make_rmq(n, [&b](const uint l, const uint r){return b[l] > b[r];});
        vector<i64> c(n, -INF);
        for(int j = 1; j < n; ++j)
            c[j] = b[seg.fold_closed(max(0, j - m), j - 1)] + a[j] * (i + 1);

        b = move(c);
    }

    cout << *max_element(b.begin(), b.end()) << endl;
}