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 ii = pair<int, int>;
 
#define fi first
#define re return
#define se second
#define in insert
#define pb push_back
#define eb emplace_back
#define y1 y123123123123
#define all(x) x.begin(), x.end()
#define hash hash123s
#define index ind123
 
#define repx(i, x, n) for (int i = x; i < (n); i++)
#define repd(i, n, d) for (int i = 0; i < (n); i += d)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepd(i, n, d) for (int i = (n) - 1; i >= 0; i -= d)
#define rep(i, n) for (int i = 0; i < (n); i++)
 
template<class t>
void print(t x, int end = 1) {
    cout << x << (end == 1 ? "\n" : " ");
}
 
template<class T>
void print(const vector<T> &v, int end = 1) {
    rep(i, (int) v.size()) {
        print(v[ i ], 0);
    }
    cout << endl;
}
 
template<class T>
void print(const set<T> &v, int end = 1) {
    for(auto to = v.begin(); to != v.end(); to++) {
        print(*to);
    }
    cout << endl;
}
 
template<class T>
void print(const map<T, T> &v, int end = 1) {
    for(auto to : v) {
        print(to.fi, 0);
        cout << ": ";
        print(to.se);
    }
}
 
template<class t>
void errprint(t x, int end = 1) {
    cerr << x << (end == 1 ? "\n" : " ");
}

#define name(x) cerr << #x << " = ";
#define errprint_var(x) cerr << #x << " = " << x << endl;
#define errprint_vec(x) { name(x); cerr << "{"; rep(i, x.size()) cerr << x[ i ] << (i == x.size() - 1 ? "" : ", "); cerr << "}" << endl; }
 
#ifdef artem
    #define debug(x) x
    #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
    #define debug(x)
#endif
 
void solve();
 
clock_t start_time;
double get_current_time() {
    return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}
 
int main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
 
    ios_base::sync_with_stdio(false);
    solve();
}
 
/* ==================== actual code starts here ==================== */

const int limitN = (int)1e5 + 123;
const int limitK = 300 + 123;
const int limit2 = 18;

int n, m, k;
ll a[ limitN ], dp[ limitK ][ limitN ]; // [ cnt ][ last pos ] = max impact
ll st[ limit2 + 1 ][ limitN ];
int p2[ limitN ];

void init_sparse(int x) {
	rep(i, n) {
		st[ 0 ][ i ] = dp[ x ][ i ];
	}
	repx(j, 1, limit2 + 1) {
		rep(i, n - (1 << j) + 1) {
			st[ j ][ i ] = max(st[ j - 1 ][ i ], st[ j - 1 ][ i + (1 << (j - 1)) ]);
		}
	}
}

ll get_max(int l, int r) {
	int lg = p2[ r - l + 1 ];
	re max(st[ lg ][ l ], st[ lg ][ r - (1 << lg) + 1 ]);
}

void solve() {
	cin >> n >> m >> k;
	rep(i, n) cin >> a[ i ];

	rep(i, n) {
		dp[ 1 ][ i ] = a[ i ];
	}
	repx(i, 2, n + 1) {
		p2[ i ] = p2[ i / 2 ] + 1;
	}

	repx(j, 2, k + 1) {
		init_sparse(j - 1);
		repx(i, j - 1, n) {
			int l = max(0, i - m), r = i - 1;
			ll mx = get_max(l, r);
			// cout << "l = " << l << ", r = " << r << " : " << mx << endl;
			dp[ j ][ i ] = max(dp[ j ][ i ], (ll)j * a[ i ] + mx);
		}
	}

	// repx(j, 1, k + 1) {
	// 	cout << "j = " << j << endl;
	// 	rep(i, n) {
	// 		print(dp[ j ][ i ], 0);
	// 	}
	// 	cout << endl;
	// }

	ll ans = 0;
	rep(i, n) ans = max(ans, dp[ k ][ i ]);
	print(ans);
}