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 <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353
using namespace std;
typedef pair<llint, llint> P;
typedef pair<llint, P> E;

struct SWAG{
	llint size;
	stack<P> head, tail;
	SWAG(){init();}
	
	llint getElement(){ //単位元e
		return -inf;
	}
	llint ope(llint x, llint y){  //作用素(x * y)
		return max(x, y);
	}
	void init(){
		size = 0;
		while(head.size()) head.pop();
		while(tail.size()) tail.pop();
	}
	void push(llint x){
		size++;
		if(tail.size() == 0){
			tail.push(P(x, x));
			return;
		}
		tail.push(P(x, ope(tail.top().second, x)));
	}
	void pop(){
		if(size == 0) return;
		if(head.size() == 0){
			llint sum = getElement();
			while(tail.size()){
				llint x = tail.top().first;
				sum = ope(x, sum);
				head.push(P(x, ope(x, sum)));
				tail.pop();
			}
		}
		head.pop();
		size--;
	}
	llint query(){
		llint ret = getElement();
		if(head.size()) ret = ope(ret, head.top().second);
		if(tail.size()) ret = ope(ret, tail.top().second);
		return ret;
	}
};

llint n, m, k;
llint a[100005];
llint dp[305][100005];
SWAG sw;

int main(void)
{
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	for(int j = 1; j <= n; j++) dp[1][j] = a[j];
	for(int i = 2; i <= k; i++){
		sw.init();
		for(int j = 1; j <= n; j++){
			dp[i][j] = sw.query() + a[j] * i;
			sw.push(dp[i-1][j]);
			if(j > m) sw.pop();
		}
	}
	
	llint ans = 0;
	for(int i = 1; i <= n; i++) ans = max(ans, dp[k][i]);
	cout << ans << endl;
	
	
	return 0;
}