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<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


struct edge
{
	long long to; long long len;
	bool operator<(const edge& rhs) const {
		return len > rhs.len;
	}
};

struct minqueue {
	deque<ll> dq;
	vector<ll> vec;
	ll head = 0;
	ll tail = 0;
	bool op(ll a, ll b) {
		return a <= b;
	}

	bool can_push(ll x) {
		if (dq.empty()) {
			return true;
		}
		else {
			return op(x, vec[dq.back()]);
		}
	}

	void push(ll x) {
		while (!can_push(x)) {
			dq.pop_back();
		}
		dq.push_back(tail);
		tail++;
		vec.push_back(x);
	}

	ll val() {
		return vec[dq.front()];
	}

	void pop() {
		if (head == dq.front()) {
			dq.pop_front();
		}
		head++;
	}
};


ll const MAX = 1e5 + 5;
vll a(MAX);
vvll dp(MAX, vll(305));


int main() {
	ll n, m, k;
	cin >> n >> m >> k;
	REP(i, 1, n) {
		cin >> a[i];
	}
	ll ans = 0;

	REP(j, 1, k) {
		minqueue mq;
		mq.push(dp[j - 1][j - 1]);
		REP(i, j, n) {
			dp[i][j] = mq.val() + j * a[i];
			mq.push(dp[i][j - 1]);
			if (i >= j + m - 1) {
				mq.pop();
			}
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
}